,An Introduction to Genetic Algorithms
n n n n
Mitchell Melanie
n
AnBradfordnBooknThenMITnPress
Cambridge,nMassachusettsn•nLondon,nEnglandn
Fifthnprinting,n1999
FirstnMITnPressnpaperbacknedition,n1998
Copyrightn©n1996nMassachusettsnInstitutenofnTechnology
Allnrightsnreserved.nNonpartnofnthisnpublicationnmaynbenreproducedninnanynformnbynanynelectronicnornm
echanicalnmeansn(includingnphotocopying,nrecording,norninformationnstoragenandnretrieval)nwithoutnpe
rmissionninnwritingnfromnthenpublisher.
SetninnPalatinonbynWindfallnSoftwarenusingnZzTEX.nL
ibrarynofnCongressnCataloging−in−PublicationnDatan
Mitchell,nMelanie.
Annintroductionntongeneticnalgorithmsn/nMelanienMitchell.
p.ncm.
"AnBradfordnbook."
Includesnbibliographicalnreferencesnandnindex.
ISBNn0−262−13316−4n(HB),n0−262−63185−7n(PB)
1. Genetics—Computernsimulation.2.nGenetics—Mathematicalnmodels.I.nTitle.
QH441.2.M55n1996
575.1'01'13—
dc20n95−24489nCIP
1
, Table of Contents
n n
AnnIntroductionntonGeneticnAlgorithms .......................................................................................................... 1
MitchellnMelanie .................................................................................................................................... 1
Chaptern1:nGeneticnAlgorithms:nAnnOverview ............................................................................................... 2
Overview ................................................................................................................................................ 2
1.1 AnBRIEFnHISTORYnOFnEVOLUTIONARYnCOMPUTATION .................................................... 2
1.2 THEnAPPEALnOFnEVOLUTION .................................................................................................... 4
1.3 BIOLOGICALnTERMINOLOGY ................................................................................................... 5
1.4 SEARCHnSPACESnANDnFITNESSnLANDSCAPES ..................................................................... 6
1.5 ELEMENTSnOFnGENETICnALGORITHMS.................................................................................. 7
ExamplesnofnFitnessnFunctions.................................................................................................. 7
GAnOperators ............................................................................................................................ 8
1.6 AnSIMPLEnGENETICnALGORITHM ............................................................................................. 8
1.7 GENETICnALGORITHMSnANDnTRADITIONALnSEARCHnMETHODS ................................. 10
1.9 TWOnBRIEFnEXAMPLES ............................................................................................................ 12
UsingnGAsntonEvolvenStrategiesnfornthenPrisoner'snDilemma .................................................. 13
HostsnandnParasites:nUsingnGAsntonEvolvenSortingnNetworks ................................................. 16
1.10 HOWnDOnGENETICnALGORITHMSnWORK? ......................................................................... 21
THOUGHTnEXERCISES .................................................................................................................... 23
COMPUTERnEXERCISES.................................................................................................................. 24
Chaptern2:nGeneticnAlgorithmsninnProblemnSolving .................................................................................... 27
Overview .............................................................................................................................................. 27
2.1 EVOLVINGnCOMPUTERnPROGRAMS ..................................................................................... 27
EvolvingnLispnPrograms.......................................................................................................... 27
EvolvingnCellularnAutomata ................................................................................................... 34
2.2 DATAnANALYSISnANDnPREDICTION ...................................................................................... 42
PredictingnDynamicalnSystems ............................................................................................... 42
PredictingnProteinnStructure .................................................................................................... 47
2.3 EVOLVINGnNEURALnNETWORKS ........................................................................................... 49
EvolvingnWeightsninnanFixednNetwork .................................................................................... 50
EvolvingnNetworknArchitectures............................................................................................. 53
DirectnEncoding ...................................................................................................................... 54
GrammaticalnEncoding ........................................................................................................... 55
EvolvingnanLearningnRule ....................................................................................................... 58
THOUGHTnEXERCISES .................................................................................................................... 60
COMPUTERnEXERCISES.................................................................................................................. 62
Chaptern3:nGeneticnAlgorithmsninnScientificnModels ................................................................................... 65
Overview .............................................................................................................................................. 65
3.1 MODELINGnINTERACTIONSnBETWEENnLEARNINGnANDnEVOLUTION .......................... 66
ThenBaldwinnEffect ................................................................................................................. 66
AnSimplenModelnofnthenBaldwinnEffect ................................................................................... 68
EvolutionarynReinforcementnLearning.................................................................................... 72
3.2 MODELINGnSEXUALnSELECTION ........................................................................................... 75
SimulationnandnElaborationnofnanMathematicalnModelnfornSexualnSelection........................... 76
3.3 MODELINGnECOSYSTEMS ....................................................................................................... 78
3.4 MEASURINGnEVOLUTIONARYnACTIVITY ............................................................................ 81
ThoughtnExercises ................................................................................................................................ 84
ComputernExercises ............................................................................................................................. 85
, Table of Contentsn n
Chaptern4:nTheoreticalnFoundationsnofnGeneticnAlgorithms....................................................................... 87
Overview .............................................................................................................................................. 87
4.1 SCHEMASnANDnTHEnTWO−ARMEDnBANDITnPROBLEM .................................................... 87
ThenTwo−ArmednBanditnProblem........................................................................................... 88
SketchnofnanSolution................................................................................................................. 89
InterpretationnofnthenSolution................................................................................................... 91
ImplicationsnfornGAnPerformance............................................................................................ 92
DeceivingnanGeneticnAlgorithm ............................................................................................... 93
Limitationsnofn"Static"nSchemanAnalysis ................................................................................. 93
4.2 ROYALnROADS ........................................................................................................................... 94
RoyalnRoadnFunctions ............................................................................................................. 94
ExperimentalnResults .............................................................................................................. 95
Steepest−ascentnhillnclimbingn(SAHC) .................................................................................... 96
Next−ascentnhillnclimbingn(NAHC) ......................................................................................... 96
Random−mutationnhillnclimbingn(RMHC) .............................................................................. 96
AnalysisnofnRandom−MutationnHillnClimbing ........................................................................ 97
HitchhikingninnthenGeneticnAlgorithm ..................................................................................... 98
AnnIdealizednGeneticnAlgorithm.............................................................................................. 99
4.3 EXACTnMATHEMATICALnMODELSnOFnSIMPLEnGENETICnALGORITHMS .................... 103
FormalizationnofnGAs............................................................................................................ 103
ResultsnofnthenFormalization .................................................................................................. 108
AnFinite−PopulationnModel .................................................................................................. 108
4.4 STATISTICAL−MECHANICSnAPPROACHES ........................................................................ 112
THOUGHTnEXERCISES .................................................................................................................. 114
COMPUTERnEXERCISES................................................................................................................ 116
5.1 WHENnSHOULDnAnGENETICnALGORITHMnBEnUSED? ....................................................... 116
5.2 ENCODINGnAnPROBLEMnFORnAnGENETICnALGORITHM .................................................. 117
BinarynEncodings .................................................................................................................. 117
Many−CharacternandnReal−ValuednEncodings ..................................................................... 118
TreenEncodings ..................................................................................................................... 118
5.3 ADAPTINGnTHEnENCODING ................................................................................................... 118
Inversion ............................................................................................................................... 119
EvolvingnCrossovern"HotnSpots" ........................................................................................... 120
MessynGas ............................................................................................................................. 121
5.4 SELECTIONnMETHODS............................................................................................................ 124
Fitness−Proportionaten Selectionn withn "Rouletten Wheel"n andn "Stochasticn Universal"nSamplin
g ........................................................................................................................................... 124
SigmanScaling ....................................................................................................................... 125
Elitism ................................................................................................................................... 126
BoltzmannnSelection ............................................................................................................. 126
RanknSelection ...................................................................................................................... 127
TournamentnSelection ........................................................................................................... 127
Steady−StatenSelection.......................................................................................................... 128
5.5 GENETICnOPERATORS ............................................................................................................ 128
Crossover .............................................................................................................................. 128
Mutation ................................................................................................................................ 129
OthernOperatorsnandnMatingnStrategies ................................................................................. 130
5.6 PARAMETERSnFORnGENETICnALGORITHMS ...................................................................... 130
THOUGHTnEXERCISES .................................................................................................................. 132
COMPUTERnEXERCISES................................................................................................................ 133
n n n n
Mitchell Melanie
n
AnBradfordnBooknThenMITnPress
Cambridge,nMassachusettsn•nLondon,nEnglandn
Fifthnprinting,n1999
FirstnMITnPressnpaperbacknedition,n1998
Copyrightn©n1996nMassachusettsnInstitutenofnTechnology
Allnrightsnreserved.nNonpartnofnthisnpublicationnmaynbenreproducedninnanynformnbynanynelectronicnornm
echanicalnmeansn(includingnphotocopying,nrecording,norninformationnstoragenandnretrieval)nwithoutnpe
rmissionninnwritingnfromnthenpublisher.
SetninnPalatinonbynWindfallnSoftwarenusingnZzTEX.nL
ibrarynofnCongressnCataloging−in−PublicationnDatan
Mitchell,nMelanie.
Annintroductionntongeneticnalgorithmsn/nMelanienMitchell.
p.ncm.
"AnBradfordnbook."
Includesnbibliographicalnreferencesnandnindex.
ISBNn0−262−13316−4n(HB),n0−262−63185−7n(PB)
1. Genetics—Computernsimulation.2.nGenetics—Mathematicalnmodels.I.nTitle.
QH441.2.M55n1996
575.1'01'13—
dc20n95−24489nCIP
1
, Table of Contents
n n
AnnIntroductionntonGeneticnAlgorithms .......................................................................................................... 1
MitchellnMelanie .................................................................................................................................... 1
Chaptern1:nGeneticnAlgorithms:nAnnOverview ............................................................................................... 2
Overview ................................................................................................................................................ 2
1.1 AnBRIEFnHISTORYnOFnEVOLUTIONARYnCOMPUTATION .................................................... 2
1.2 THEnAPPEALnOFnEVOLUTION .................................................................................................... 4
1.3 BIOLOGICALnTERMINOLOGY ................................................................................................... 5
1.4 SEARCHnSPACESnANDnFITNESSnLANDSCAPES ..................................................................... 6
1.5 ELEMENTSnOFnGENETICnALGORITHMS.................................................................................. 7
ExamplesnofnFitnessnFunctions.................................................................................................. 7
GAnOperators ............................................................................................................................ 8
1.6 AnSIMPLEnGENETICnALGORITHM ............................................................................................. 8
1.7 GENETICnALGORITHMSnANDnTRADITIONALnSEARCHnMETHODS ................................. 10
1.9 TWOnBRIEFnEXAMPLES ............................................................................................................ 12
UsingnGAsntonEvolvenStrategiesnfornthenPrisoner'snDilemma .................................................. 13
HostsnandnParasites:nUsingnGAsntonEvolvenSortingnNetworks ................................................. 16
1.10 HOWnDOnGENETICnALGORITHMSnWORK? ......................................................................... 21
THOUGHTnEXERCISES .................................................................................................................... 23
COMPUTERnEXERCISES.................................................................................................................. 24
Chaptern2:nGeneticnAlgorithmsninnProblemnSolving .................................................................................... 27
Overview .............................................................................................................................................. 27
2.1 EVOLVINGnCOMPUTERnPROGRAMS ..................................................................................... 27
EvolvingnLispnPrograms.......................................................................................................... 27
EvolvingnCellularnAutomata ................................................................................................... 34
2.2 DATAnANALYSISnANDnPREDICTION ...................................................................................... 42
PredictingnDynamicalnSystems ............................................................................................... 42
PredictingnProteinnStructure .................................................................................................... 47
2.3 EVOLVINGnNEURALnNETWORKS ........................................................................................... 49
EvolvingnWeightsninnanFixednNetwork .................................................................................... 50
EvolvingnNetworknArchitectures............................................................................................. 53
DirectnEncoding ...................................................................................................................... 54
GrammaticalnEncoding ........................................................................................................... 55
EvolvingnanLearningnRule ....................................................................................................... 58
THOUGHTnEXERCISES .................................................................................................................... 60
COMPUTERnEXERCISES.................................................................................................................. 62
Chaptern3:nGeneticnAlgorithmsninnScientificnModels ................................................................................... 65
Overview .............................................................................................................................................. 65
3.1 MODELINGnINTERACTIONSnBETWEENnLEARNINGnANDnEVOLUTION .......................... 66
ThenBaldwinnEffect ................................................................................................................. 66
AnSimplenModelnofnthenBaldwinnEffect ................................................................................... 68
EvolutionarynReinforcementnLearning.................................................................................... 72
3.2 MODELINGnSEXUALnSELECTION ........................................................................................... 75
SimulationnandnElaborationnofnanMathematicalnModelnfornSexualnSelection........................... 76
3.3 MODELINGnECOSYSTEMS ....................................................................................................... 78
3.4 MEASURINGnEVOLUTIONARYnACTIVITY ............................................................................ 81
ThoughtnExercises ................................................................................................................................ 84
ComputernExercises ............................................................................................................................. 85
, Table of Contentsn n
Chaptern4:nTheoreticalnFoundationsnofnGeneticnAlgorithms....................................................................... 87
Overview .............................................................................................................................................. 87
4.1 SCHEMASnANDnTHEnTWO−ARMEDnBANDITnPROBLEM .................................................... 87
ThenTwo−ArmednBanditnProblem........................................................................................... 88
SketchnofnanSolution................................................................................................................. 89
InterpretationnofnthenSolution................................................................................................... 91
ImplicationsnfornGAnPerformance............................................................................................ 92
DeceivingnanGeneticnAlgorithm ............................................................................................... 93
Limitationsnofn"Static"nSchemanAnalysis ................................................................................. 93
4.2 ROYALnROADS ........................................................................................................................... 94
RoyalnRoadnFunctions ............................................................................................................. 94
ExperimentalnResults .............................................................................................................. 95
Steepest−ascentnhillnclimbingn(SAHC) .................................................................................... 96
Next−ascentnhillnclimbingn(NAHC) ......................................................................................... 96
Random−mutationnhillnclimbingn(RMHC) .............................................................................. 96
AnalysisnofnRandom−MutationnHillnClimbing ........................................................................ 97
HitchhikingninnthenGeneticnAlgorithm ..................................................................................... 98
AnnIdealizednGeneticnAlgorithm.............................................................................................. 99
4.3 EXACTnMATHEMATICALnMODELSnOFnSIMPLEnGENETICnALGORITHMS .................... 103
FormalizationnofnGAs............................................................................................................ 103
ResultsnofnthenFormalization .................................................................................................. 108
AnFinite−PopulationnModel .................................................................................................. 108
4.4 STATISTICAL−MECHANICSnAPPROACHES ........................................................................ 112
THOUGHTnEXERCISES .................................................................................................................. 114
COMPUTERnEXERCISES................................................................................................................ 116
5.1 WHENnSHOULDnAnGENETICnALGORITHMnBEnUSED? ....................................................... 116
5.2 ENCODINGnAnPROBLEMnFORnAnGENETICnALGORITHM .................................................. 117
BinarynEncodings .................................................................................................................. 117
Many−CharacternandnReal−ValuednEncodings ..................................................................... 118
TreenEncodings ..................................................................................................................... 118
5.3 ADAPTINGnTHEnENCODING ................................................................................................... 118
Inversion ............................................................................................................................... 119
EvolvingnCrossovern"HotnSpots" ........................................................................................... 120
MessynGas ............................................................................................................................. 121
5.4 SELECTIONnMETHODS............................................................................................................ 124
Fitness−Proportionaten Selectionn withn "Rouletten Wheel"n andn "Stochasticn Universal"nSamplin
g ........................................................................................................................................... 124
SigmanScaling ....................................................................................................................... 125
Elitism ................................................................................................................................... 126
BoltzmannnSelection ............................................................................................................. 126
RanknSelection ...................................................................................................................... 127
TournamentnSelection ........................................................................................................... 127
Steady−StatenSelection.......................................................................................................... 128
5.5 GENETICnOPERATORS ............................................................................................................ 128
Crossover .............................................................................................................................. 128
Mutation ................................................................................................................................ 129
OthernOperatorsnandnMatingnStrategies ................................................................................. 130
5.6 PARAMETERSnFORnGENETICnALGORITHMS ...................................................................... 130
THOUGHTnEXERCISES .................................................................................................................. 132
COMPUTERnEXERCISES................................................................................................................ 133
