Significance of encoding scheme in Genetic Algorithms
$begingroup$
In the basic structure of a genetic algorithm, we have a population which is iteratively changed via selection, crossover, and mutation. Roughly:
selection biases the procedure towards individuals with high fitness,
crossover combines individuals to generate new individuals,
mutation perturbs individuals to generate new individuals which may be completely foreign to what's been seen before.
Intuitively, as an optimization routine, a prerequisite to making this effective should be some assumption of smoothness in the fitness landscape (the function from encoded string to fitness value). Without that assumption (and considering each step separately) [1]:
selection would function like a random search/random sampling,
crossover would send you to an arbitrary location in the landscape, with no guarantees that a combination of parents actually takes any of their (desirable or not) traits,
mutation would not necessary give you a neighbor of your parent (in the fitness sense or even in the sense of having mostly similar traits) - again it can send you to a random location in the landscape.
So without that smoothness assumption, it seems none of the operations are any better than random search/random sampling. Admittedly, any kind of non-exhaustive optimization routine implicitly or otherwise makes at least some smoothness assumptions (simulated annealing and hill climbing both assume neighbors of current state should have closer objective value than a random candidate). What's interesting in the case of a genetic algorithm is that we do not directly operate on the parameters - so there is a chance for/a requirement that the encoding scheme is designed such that the fitness landscape is smooth.
I haven't seen any explicit mention of this idea in the theory. Is this actually a concern? If so, should we be designing encoding schemes so that there's a higher chance that crossover and mutation produce true "neighbors" of their inputs?
[1] I'm aware that the Schema Theorem implies the entire procedure works differently, and does not necessarily require any short of "neighbor" relationship be maintained across the operators. However, it seems even that idea requires some structure from the schemas: "11**" ought to be closer to "1***" than to "0***", but one can imagine a encoding where that's not the case; additionally, "11**" appear equidistant to "10**" and "01**", but in the case where the first digit represents a trait and the second a parameter of the trait, "10**" would be a true neighbor but "01**" would be completely unrelated.
optimization
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
$endgroup$
add a comment |
$begingroup$
In the basic structure of a genetic algorithm, we have a population which is iteratively changed via selection, crossover, and mutation. Roughly:
selection biases the procedure towards individuals with high fitness,
crossover combines individuals to generate new individuals,
mutation perturbs individuals to generate new individuals which may be completely foreign to what's been seen before.
Intuitively, as an optimization routine, a prerequisite to making this effective should be some assumption of smoothness in the fitness landscape (the function from encoded string to fitness value). Without that assumption (and considering each step separately) [1]:
selection would function like a random search/random sampling,
crossover would send you to an arbitrary location in the landscape, with no guarantees that a combination of parents actually takes any of their (desirable or not) traits,
mutation would not necessary give you a neighbor of your parent (in the fitness sense or even in the sense of having mostly similar traits) - again it can send you to a random location in the landscape.
So without that smoothness assumption, it seems none of the operations are any better than random search/random sampling. Admittedly, any kind of non-exhaustive optimization routine implicitly or otherwise makes at least some smoothness assumptions (simulated annealing and hill climbing both assume neighbors of current state should have closer objective value than a random candidate). What's interesting in the case of a genetic algorithm is that we do not directly operate on the parameters - so there is a chance for/a requirement that the encoding scheme is designed such that the fitness landscape is smooth.
I haven't seen any explicit mention of this idea in the theory. Is this actually a concern? If so, should we be designing encoding schemes so that there's a higher chance that crossover and mutation produce true "neighbors" of their inputs?
[1] I'm aware that the Schema Theorem implies the entire procedure works differently, and does not necessarily require any short of "neighbor" relationship be maintained across the operators. However, it seems even that idea requires some structure from the schemas: "11**" ought to be closer to "1***" than to "0***", but one can imagine a encoding where that's not the case; additionally, "11**" appear equidistant to "10**" and "01**", but in the case where the first digit represents a trait and the second a parameter of the trait, "10**" would be a true neighbor but "01**" would be completely unrelated.
optimization
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
$endgroup$
$begingroup$
Richard Dawkins' "Climbing Mount Improbable" has an extensive discussion of the impacts of the fitness landscape on evolution. It is oriented toward living things, but the ideas apply. He talks about the differences between a large smooth plain and a mountainous landscape in detail.
$endgroup$
– Ross Millikan
Jan 1 at 17:08
$begingroup$
Natural selection is one of nature's most formidable design tools.
$endgroup$
– Cesareo
Jan 1 at 17:13
add a comment |
$begingroup$
In the basic structure of a genetic algorithm, we have a population which is iteratively changed via selection, crossover, and mutation. Roughly:
selection biases the procedure towards individuals with high fitness,
crossover combines individuals to generate new individuals,
mutation perturbs individuals to generate new individuals which may be completely foreign to what's been seen before.
Intuitively, as an optimization routine, a prerequisite to making this effective should be some assumption of smoothness in the fitness landscape (the function from encoded string to fitness value). Without that assumption (and considering each step separately) [1]:
selection would function like a random search/random sampling,
crossover would send you to an arbitrary location in the landscape, with no guarantees that a combination of parents actually takes any of their (desirable or not) traits,
mutation would not necessary give you a neighbor of your parent (in the fitness sense or even in the sense of having mostly similar traits) - again it can send you to a random location in the landscape.
So without that smoothness assumption, it seems none of the operations are any better than random search/random sampling. Admittedly, any kind of non-exhaustive optimization routine implicitly or otherwise makes at least some smoothness assumptions (simulated annealing and hill climbing both assume neighbors of current state should have closer objective value than a random candidate). What's interesting in the case of a genetic algorithm is that we do not directly operate on the parameters - so there is a chance for/a requirement that the encoding scheme is designed such that the fitness landscape is smooth.
I haven't seen any explicit mention of this idea in the theory. Is this actually a concern? If so, should we be designing encoding schemes so that there's a higher chance that crossover and mutation produce true "neighbors" of their inputs?
[1] I'm aware that the Schema Theorem implies the entire procedure works differently, and does not necessarily require any short of "neighbor" relationship be maintained across the operators. However, it seems even that idea requires some structure from the schemas: "11**" ought to be closer to "1***" than to "0***", but one can imagine a encoding where that's not the case; additionally, "11**" appear equidistant to "10**" and "01**", but in the case where the first digit represents a trait and the second a parameter of the trait, "10**" would be a true neighbor but "01**" would be completely unrelated.
optimization
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
$endgroup$
In the basic structure of a genetic algorithm, we have a population which is iteratively changed via selection, crossover, and mutation. Roughly:
selection biases the procedure towards individuals with high fitness,
crossover combines individuals to generate new individuals,
mutation perturbs individuals to generate new individuals which may be completely foreign to what's been seen before.
Intuitively, as an optimization routine, a prerequisite to making this effective should be some assumption of smoothness in the fitness landscape (the function from encoded string to fitness value). Without that assumption (and considering each step separately) [1]:
selection would function like a random search/random sampling,
crossover would send you to an arbitrary location in the landscape, with no guarantees that a combination of parents actually takes any of their (desirable or not) traits,
mutation would not necessary give you a neighbor of your parent (in the fitness sense or even in the sense of having mostly similar traits) - again it can send you to a random location in the landscape.
So without that smoothness assumption, it seems none of the operations are any better than random search/random sampling. Admittedly, any kind of non-exhaustive optimization routine implicitly or otherwise makes at least some smoothness assumptions (simulated annealing and hill climbing both assume neighbors of current state should have closer objective value than a random candidate). What's interesting in the case of a genetic algorithm is that we do not directly operate on the parameters - so there is a chance for/a requirement that the encoding scheme is designed such that the fitness landscape is smooth.
I haven't seen any explicit mention of this idea in the theory. Is this actually a concern? If so, should we be designing encoding schemes so that there's a higher chance that crossover and mutation produce true "neighbors" of their inputs?
[1] I'm aware that the Schema Theorem implies the entire procedure works differently, and does not necessarily require any short of "neighbor" relationship be maintained across the operators. However, it seems even that idea requires some structure from the schemas: "11**" ought to be closer to "1***" than to "0***", but one can imagine a encoding where that's not the case; additionally, "11**" appear equidistant to "10**" and "01**", but in the case where the first digit represents a trait and the second a parameter of the trait, "10**" would be a true neighbor but "01**" would be completely unrelated.
optimization
optimization
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
asked Jan 1 at 16:59
Roasted YamRoasted Yam
132
132
$begingroup$
Richard Dawkins' "Climbing Mount Improbable" has an extensive discussion of the impacts of the fitness landscape on evolution. It is oriented toward living things, but the ideas apply. He talks about the differences between a large smooth plain and a mountainous landscape in detail.
$endgroup$
– Ross Millikan
Jan 1 at 17:08
$begingroup$
Natural selection is one of nature's most formidable design tools.
$endgroup$
– Cesareo
Jan 1 at 17:13
add a comment |
$begingroup$
Richard Dawkins' "Climbing Mount Improbable" has an extensive discussion of the impacts of the fitness landscape on evolution. It is oriented toward living things, but the ideas apply. He talks about the differences between a large smooth plain and a mountainous landscape in detail.
$endgroup$
– Ross Millikan
Jan 1 at 17:08
$begingroup$
Natural selection is one of nature's most formidable design tools.
$endgroup$
– Cesareo
Jan 1 at 17:13
$begingroup$
Richard Dawkins' "Climbing Mount Improbable" has an extensive discussion of the impacts of the fitness landscape on evolution. It is oriented toward living things, but the ideas apply. He talks about the differences between a large smooth plain and a mountainous landscape in detail.
$endgroup$
– Ross Millikan
Jan 1 at 17:08
$begingroup$
Richard Dawkins' "Climbing Mount Improbable" has an extensive discussion of the impacts of the fitness landscape on evolution. It is oriented toward living things, but the ideas apply. He talks about the differences between a large smooth plain and a mountainous landscape in detail.
$endgroup$
– Ross Millikan
Jan 1 at 17:08
$begingroup$
Natural selection is one of nature's most formidable design tools.
$endgroup$
– Cesareo
Jan 1 at 17:13
$begingroup$
Natural selection is one of nature's most formidable design tools.
$endgroup$
– Cesareo
Jan 1 at 17:13
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3058656%2fsignificance-of-encoding-scheme-in-genetic-algorithms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3058656%2fsignificance-of-encoding-scheme-in-genetic-algorithms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Richard Dawkins' "Climbing Mount Improbable" has an extensive discussion of the impacts of the fitness landscape on evolution. It is oriented toward living things, but the ideas apply. He talks about the differences between a large smooth plain and a mountainous landscape in detail.
$endgroup$
– Ross Millikan
Jan 1 at 17:08
$begingroup$
Natural selection is one of nature's most formidable design tools.
$endgroup$
– Cesareo
Jan 1 at 17:13