No Free Lunch? (Delayed reply)

[Pau Bofill]

(I've just been added to the Connectionists list, 
and therefore I apologize if I'm repeating something that's been
said before.)

I happened to read the message from Bill Macready on Free Lunch
Theorems for Search, and I was surprised
by his (and D.H. Wolpert's) statement that

	"any two search algorithms have exactly the same expected
	performance, over the space of all fitness functions."

which seemed to invalidate statements like

	"my search algorithm beats your search algorithm according 
	to a particular performance measure for the following fitness
	function."

Thus, I picked the papers anounced on that message (see below) and tryied to find
out what did they mean. 

As far as I can see, the goal of a particular optimization PROBLEM, is
to find a target POINT in search space whith specific properties.
The role of any fitness function, then, is to assign a cost value to
each point in search space in such a way that it helps the algorithm
beeing used to find the target point. In particular, for optimization
purposes, a necessary condition for the validity of a fitness 
function is that it assigns the maximum (or minimum) cost value 
to all valid target points, and only to target points.

If I understood them properly, Wolpert and Macready define the 
space of all possible fitness functions as the set of ALL possible assignments
of cost values to points in search space.
And they use as a generalized perfomace measure the histogram of cost values, 
regardless of the points where they were found. 
Then, if what I understood is right, 
they are ignoring the previous necessary condition on fitness functions
and their statement is equivalent to,

	"any two search algorithms have exactly the same expected
	performance, over the space of all optimization problems
	that can be defined whithin a search space."

which stated otherwise would mean,

	"If the target doesn't matter, all algorithms perform alike."

I don't doubt that Wolpert & Macready's "No Free Lunch Theorem"
can be useful as a tool for deriving further results, but one 
should be carefull when considering its "physical" meaning.

Thus, I believe it is very important to define carefully the meaning
of,

	"My algorithm performs better than yours."

In particular, algorithms should be compared on PROBLEMS, not on
fitness functions, with properly defined performance measures.
Probably, the most fair one-to-one comparision would use the best (found)
fitness function for each algorithm (finding the best fitness function
for a particular problem AND algorithm is, in turn, an optimization problem). 

Averaging over algorithms in order to measure problem hardness is 
"dangerous" in the same sense.


Pau Bofill
Universitat Politecnica de Catalunya.

**************************************************************************

The papers mentioned are at
	
	ftp.santafe.edu

	/pub/wgm/nfl.ps
	        /hard.ps