Evolutionary algorithms assume that the route to an optimal solution is paved with progressively better solutions.
This isn't true. When this is the case, every mutation that increases fitness is a move in the "right direction", so you just have one big fitness hill. But then you don't even need real evolution! Just take one individual, examine some possible single-mutations from it until you get something better. Keep repeating, and you're guaranteed to get an optimal solution in the end. We called these "stochastic hill-climbers," IIRC.
Notice that the ONE-MAX example is like this. Every new 1-character you get in the string gene is a step in the right direction, up the hypercube so to speak. This might be a reason why ONE-MAX is a deceptively simple first example?
This is not be true for some problems, so it's important to keep that in mind.
You're exactly right here. I wanted to imply this by mentioning suboptimal fitness hills, but it's probably better to say it explicitly. By climbing up a suboptimal hill, you are taking steps "up", but you won't get to an optimal solution. To get to an optimal solution, must to take steps "down" the hill first. So the route to an optimal solution isn't paved with progressively better things. This is why we don't want to kill off lower-fitness individuals as soon as we lay eyes on them in hard problems ;) .. if they have a chance of breeding, they might even lead us up a different fitness hill than the one we're stuck on.
One more thing: at my school we call them genetic algorithms
I never got most of these silly and similar-sounding terms straight in my head! According to the EA FAQ, EA encompasses genetic algorithms. However, the psuedocode they give for both seems the same. So I honestly don't know the difference. It's seems pretty safe to interchange the two terms, and definitely within the structure laid out in my writeup (which follows the pseudocode of both).
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|
