Engelbrecht Andries P. Computational Intelligence: An Introduction
Подождите немного. Документ загружается.
viii CONTENTS
3.1.4 SimpleRecurrentNeuralNetworks................ 32
3.1.5 Time-DelayNeuralNetworks ................... 34
3.1.6 CascadeNetworks ......................... 35
3.2 SupervisedLearningRules......................... 36
3.2.1 TheSupervisedLearningProblem ................ 36
3.2.2 GradientDescentOptimization.................. 38
3.2.3 ScaledConjugateGradient .................... 45
3.2.4 LeapFrogOptimization ...................... 49
3.2.5 ParticleSwarmOptimization ................... 49
3.3 FunctioningofHiddenUnits........................ 49
3.4 EnsembleNeuralNetworks ........................ 51
3.5 Assignments................................. 54
4 Unsupervised Learning Neural Networks 55
4.1 Background................................. 55
4.2 HebbianLearningRule........................... 56
4.3 PrincipalComponentLearningRule ................... 58
4.4 LearningVectorQuantizer-I........................ 59
4.5 Self-Organizing Feature Maps ....................... 62
4.5.1 StochasticTrainingRule...................... 62
4.5.2 BatchMap ............................. 65
4.5.3 GrowingSOM ........................... 65
4.5.4 ImprovingConvergenceSpeed................... 67
4.5.5 ClusteringandVisualization ................... 69
4.5.6 UsingSOM ............................. 71
4.6 Assignments................................. 71
5 Radial Basis Function Networks 73
5.1 LearningVectorQuantizer-II ....................... 73
5.2 RadialBasisFunctionNeuralNetworks ................. 73
5.2.1 RadialBasisFunctionNetworkArchitecture........... 74
5.2.2 RadialBasisFunctions....................... 75
5.2.3 TrainingAlgorithms ........................ 76
5.2.4 RadialBasisFunctionNetworkVariations............ 80
5.3 Assignments................................. 81
6 Reinforcement Learning 83
6.1 LearningthroughAwards ......................... 83
6.2 Model-FreeReinforcementLearningModel ............... 86
6.2.1 Temporal Difference Learning ................... 86
6.2.2 Q-Learning ............................. 86
CONTENTS ix
6.3 NeuralNetworksandReinforcementLearning.............. 87
6.3.1 RPROP............................... 87
6.3.2 GradientDescentReinforcementLearning............ 88
6.3.3 ConnectionistQ-Learning ..................... 89
6.4 Assignments................................. 91
7 Performance Issues (Supervised Learning) 93
7.1 PerformanceMeasures........................... 93
7.1.1 Accuracy .............................. 93
7.1.2 Complexity ............................. 98
7.1.3 Convergence ............................ 98
7.2 AnalysisofPerformance.......................... 98
7.3 PerformanceFactors ............................ 99
7.3.1 DataPreparation.......................... 99
7.3.2 WeightInitialization........................ 106
7.3.3 LearningRateandMomentum .................. 107
7.3.4 OptimizationMethod ....................... 109
7.3.5 ArchitectureSelection ....................... 109
7.3.6 AdaptiveActivationFunctions .................. 115
7.3.7 ActiveLearning........................... 116
7.4 Assignments................................. 124
Part III EVOLUTIONARY COMPUTATION 125
8 Introduction to Evolutionary Computation 127
8.1 Generic Evolutionary Algorithm ..................... 128
8.2 Representation–TheChromosome.................... 129
8.3 InitialPopulation.............................. 132
8.4 FitnessFunction .............................. 133
8.5 Selection................................... 134
8.5.1 SelectivePressure ......................... 135
8.5.2 RandomSelection ......................... 135
8.5.3 ProportionalSelection....................... 135
8.5.4 TournamentSelection ....................... 137
8.5.5 Rank-BasedSelection ....................... 137
8.5.6 BoltzmannSelection........................ 138
8.5.7 (µ
+
,λ)-Selection .......................... 139
8.5.8 Elitism ............................... 139
8.5.9 HallofFame ............................ 139
8.6 ReproductionOperators.......................... 139
x CONTENTS
8.7 StoppingConditions ............................ 140
8.8 EvolutionaryComputationversusClassicalOptimization ....... 141
8.9 Assignments................................. 141
9 Genetic Algorithms 143
9.1 CanonicalGeneticAlgorithm ....................... 143
9.2 Crossover .................................. 144
9.2.1 BinaryRepresentations ...................... 145
9.2.2 Floating-PointRepresentation................... 146
9.3 Mutation .................................. 153
9.3.1 BinaryRepresentations ...................... 154
9.3.2 Floating-PointRepresentations .................. 155
9.3.3 MacromutationOperator–HeadlessChicken .......... 156
9.4 ControlParameters............................. 156
9.5 GeneticAlgorithmVariants ........................ 157
9.5.1 GenerationGapMethods ..................... 158
9.5.2 MessyGeneticAlgorithms..................... 159
9.5.3 InteractiveEvolution........................ 161
9.5.4 IslandGeneticAlgorithms..................... 162
9.6 AdvancedTopics .............................. 164
9.6.1 Niching Genetic Algorithms .................... 165
9.6.2 ConstraintHandling ........................ 169
9.6.3 Multi-ObjectiveOptimization................... 170
9.6.4 DynamicEnvironments ...................... 173
9.7 Applications................................. 174
9.8 Assignments................................. 175
10 Genetic Programming 177
10.1Tree-BasedRepresentation......................... 177
10.2InitialPopulation.............................. 179
10.3FitnessFunction .............................. 180
10.4CrossoverOperators ............................ 180
10.5MutationOperators ............................ 182
10.6BuildingBlockGeneticProgramming .................. 184
10.7Applications................................. 184
10.8Assignments................................. 185
11 Evolutionary Programming 187
11.1BasicEvolutionaryProgramming..................... 187
11.2 Evolutionary Programming Operators .................. 189
11.2.1 MutationOperators ........................ 189
CONTENTS xi
11.2.2 SelectionOperators ........................ 193
11.3StrategyParameters ............................ 195
11.3.1 StaticStrategyParameters .................... 195
11.3.2 DynamicStrategies......................... 195
11.3.3 Self-Adaptation........................... 198
11.4 Evolutionary Programming Implementations . . . ........... 200
11.4.1 ClassicalEvolutionaryProgramming............... 200
11.4.2 FastEvolutionaryProgramming ................. 201
11.4.3 ExponentialEvolutionaryProgramming............. 201
11.4.4 Accelerated Evolutionary Programming . ............ 201
11.4.5 Momentum Evolutionary Programming ............. 202
11.4.6 EvolutionaryProgrammingwithLocalSearch.......... 203
11.4.7 EvolutionaryProgrammingwithExtinction........... 203
11.4.8 HybridwithParticleSwarmOptimization............ 204
11.5AdvancedTopics .............................. 206
11.5.1 ConstraintHandlingApproaches ................. 206
11.5.2 Multi-ObjectiveOptimizationandNiching ........... 206
11.5.3 DynamicEnvironments ...................... 206
11.6Applications................................. 207
11.6.1 Finite-StateMachines ....................... 207
11.6.2 FunctionOptimization....................... 208
11.6.3 TrainingNeuralNetworks..................... 209
11.6.4 Real-WorldApplications...................... 210
11.7Assignments................................. 210
12 Evolution Strategies 213
12.1(1+1)-ES.................................. 213
12.2GenericEvolutionStrategyAlgorithm .................. 215
12.3StrategyParametersandSelf-Adaptation ................ 216
12.3.1 StrategyParameterTypes..................... 216
12.3.2 StrategyParameterVariants ................... 218
12.3.3 Self-AdaptationStrategies..................... 219
12.4EvolutionStrategyOperators....................... 221
12.4.1 SelectionOperators ........................ 221
12.4.2 CrossoverOperators ........................ 222
12.4.3 MutationOperators ........................ 224
12.5EvolutionStrategyVariants........................ 226
12.5.1 PolarEvolutionStrategies..................... 226
12.5.2 EvolutionStrategieswithDirectedVariation .......... 227
xii CONTENTS
12.5.3 IncrementalEvolutionStrategies ................. 228
12.5.4 Surrogate Evolution Strategy ................... 229
12.6AdvancedTopics .............................. 229
12.6.1 ConstraintHandlingApproaches ................. 229
12.6.2 Multi-ObjectiveOptimization................... 230
12.6.3 DynamicandNoisyEnvironments ................ 233
12.6.4 Niching ............................... 233
12.7ApplicationsofEvolutionStrategies ................... 235
12.8Assignments................................. 235
13 Differential Evolution 237
13.1BasicDifferentialEvolution ........................ 237
13.1.1 DifferenceVectors ......................... 238
13.1.2 Mutation .............................. 239
13.1.3 Crossover .............................. 239
13.1.4 Selection .............................. 240
13.1.5 GeneralDifferentialEvolutionAlgorithm ............ 241
13.1.6 ControlParameters ........................ 241
13.1.7 GeometricalIllustration ...................... 242
13.2 DE/x/y/z .................................. 242
13.3VariationstoBasicDifferentialEvolution ................ 245
13.3.1 HybridDifferentialEvolutionStrategies ............. 245
13.3.2 Population-BasedDifferentialEvolution ............. 250
13.3.3 Self-AdaptiveDifferentialEvolution ............... 250
13.4DifferentialEvolutionforDiscrete-ValuedProblems........... 252
13.4.1 AngleModulatedDifferentialEvolution ............. 253
13.4.2 BinaryDifferentialEvolution ................... 254
13.5AdvancedTopics .............................. 255
13.5.1 ConstraintHandlingApproaches ................. 256
13.5.2 Multi-ObjectiveOptimization................... 256
13.5.3 DynamicEnvironments ...................... 257
13.6Applications................................. 259
13.7Assignments................................. 259
14 Cultural Algorithms 261
14.1CultureandArtificialCulture....................... 261
14.2 Basic Cultural Algorithm ......................... 262
14.3BeliefSpace................................. 263
14.3.1 KnowledgeComponents...................... 264
14.3.2 Acceptance Functions ....................... 265
CONTENTS xiii
14.3.3 AdjustingtheBeliefSpace..................... 266
14.3.4 Influence Functions ......................... 267
14.4 Fuzzy Cultural Algorithm ......................... 268
14.4.1 Fuzzy Acceptance Function .................... 269
14.4.2 FuzzifiedBeliefSpace ....................... 269
14.4.3 Fuzzy Influence Function . . . .................. 270
14.5AdvancedTopics .............................. 271
14.5.1 ConstraintHandling ........................ 271
14.5.2 Multi-ObjectiveOptimization................... 272
14.5.3 DynamicEnvironments ...................... 273
14.6Applications................................. 274
14.7Assignments................................. 274
15 Coevolution 275
15.1CoevolutionTypes ............................. 276
15.2CompetitiveCoevolution.......................... 276
15.2.1 CompetitiveFitness ........................ 277
15.2.2 Generic Competitive Coevolutionary Algorithm . . ....... 279
15.2.3 ApplicationsofCompetitiveCoevolution ............ 280
15.3CooperativeCoevolution.......................... 281
15.4Assignments................................. 283
Part IV COMPUTATIONAL SWARM INTELLIGENCE 285
16 Particle Swarm Optimization 289
16.1BasicParticleSwarmOptimization.................... 289
16.1.1 GlobalBestPSO.......................... 290
16.1.2 LocalBestPSO........................... 291
16.1.3 gbest versus lbest PSO ....................... 292
16.1.4 VelocityComponents........................ 293
16.1.5 GeometricIllustration ....................... 294
16.1.6 Algorithm Aspects ......................... 296
16.2SocialNetworkStructures......................... 300
16.3BasicVariations .............................. 303
16.3.1 VelocityClamping ......................... 303
16.3.2 InertiaWeight ........................... 306
16.3.3 ConstrictionCoefficient ...................... 309
16.3.4 SynchronousversusAsynchronousUpdates ........... 310
16.3.5 VelocityModels........................... 310
16.4 Basic PSO Parameters . .......................... 312
xiv CONTENTS
16.5Single-SolutionParticleSwarmOptimization .............. 314
16.5.1 GuaranteedConvergencePSO .................. 316
16.5.2 Social-BasedParticleSwarmOptimization............ 317
16.5.3 Hybrid Algorithms ......................... 321
16.5.4 Sub-Swarm Based PSO . . . ................... 326
16.5.5 Multi-Start PSO Algorithms ................... 333
16.5.6 Repelling Methods ......................... 337
16.5.7 BinaryPSO............................. 340
16.6AdvancedTopics .............................. 342
16.6.1 ConstraintHandlingApproaches ................. 342
16.6.2 Multi-ObjectiveOptimization................... 343
16.6.3 DynamicEnvironments ...................... 346
16.6.4 NichingPSO ............................ 350
16.7Applications................................. 354
16.7.1 NeuralNetworks .......................... 354
16.7.2 ArchitectureSelection ....................... 356
16.7.3 GameLearning........................... 356
16.8Assignments................................. 357
17 Ant Algorithms 359
17.1AntColonyOptimizationMeta-Heuristic ................ 360
17.1.1 Foraging Behavior of Ants . . ................... 360
17.1.2 StigmergyandArtificialPheromone ............... 363
17.1.3 SimpleAntColonyOptimization................. 364
17.1.4 AntSystem............................. 368
17.1.5 AntColonySystem......................... 372
17.1.6 Max-MinAntSystem ....................... 375
17.1.7 Ant-Q................................ 378
17.1.8 FastAntSystem .......................... 379
17.1.9 Antabu ............................... 380
17.1.10AS-rank............................... 380
17.1.11ANTS................................ 381
17.1.12ParameterSettings......................... 383
17.2CemeteryOrganizationandBroodCare ................. 384
17.2.1 BasicAntColonyClusteringModel ............... 385
17.2.2 GeneralizedAntColonyClusteringModel............ 386
17.2.3 MinimalModelforAntClustering ................ 391
17.3DivisionofLabor.............................. 391
17.3.1 DivisionofLaborinInsectColonies ............... 392
CONTENTS xv
17.3.2 TaskAllocationBasedonResponseThresholds......... 393
17.3.3 AdaptiveTaskAllocationandSpecialization .......... 395
17.4AdvancedTopics .............................. 396
17.4.1 ContinuousAntColonyOptimization .............. 396
17.4.2 Multi-ObjectiveOptimization................... 398
17.4.3 DynamicEnvironments ...................... 402
17.5Applications................................. 405
17.5.1 TravelingSalesmanProblem ................... 406
17.5.2 QuadraticAssignmentProblem.................. 407
17.5.3 OtherApplications......................... 411
17.6Assignments................................. 411
Part V ARTIFICIAL IMMUNE SYSTEMS 413
18 Natural Immune System 415
18.1ClassicalView ............................... 415
18.2AntibodiesandAntigens.......................... 416
18.3TheWhiteCells .............................. 416
18.3.1 TheLymphocytes ......................... 417
18.4ImmunityTypes .............................. 421
18.5LearningtheAntigenStructure...................... 421
18.6TheNetworkTheory............................ 422
18.7TheDangerTheory ............................ 422
18.8Assignments................................. 424
19 Artificial Immune Models 425
19.1 Artificial Immune System Algorithm . .................. 426
19.2ClassicalViewModels ........................... 428
19.2.1 NegativeSelection ......................... 428
19.2.2 Evolutionary Approaches . .................... 429
19.3ClonalSelectionTheoryModels...................... 431
19.3.1 CLONALG ............................. 431
19.3.2 DynamicClonalSelection..................... 433
19.3.3 Multi-LayeredAIS ......................... 433
19.4NetworkTheoryModels .......................... 436
19.4.1 ArtificialImmuneNetwork .................... 436
19.4.2 Self Stabilizing AIS ......................... 438
19.4.3 EnhancedArtificialImmuneNetwork .............. 440
19.4.4 DynamicWeightedB-CellAIS .................. 441
19.4.5 AdaptedArtificialImmuneNetwork ............... 442
xvi CONTENTS
19.4.6 aiNet ................................ 442
19.5DangerTheoryModels........................... 445
19.5.1 MobileAd-HocNetworks ..................... 445
19.5.2 AnAdaptiveMailbox ....................... 446
19.5.3 IntrusionDetection......................... 448
19.6ApplicationsandOtherAISmodels ................... 448
19.7Assignments................................. 448
Part VI FUZZY SYSTEMS 451
20 Fuzzy Sets 453
20.1FormalDefinitions ............................. 454
20.2MembershipFunctions........................... 454
20.3FuzzyOperators .............................. 457
20.4FuzzySetCharacteristics ......................... 459
20.5 Fuzziness and Probability ......................... 462
20.6Assignments................................. 463
21 Fuzzy Logic and Reasoning 465
21.1FuzzyLogic................................. 465
21.1.1 LinguisticsVariablesandHedges................. 466
21.1.2 FuzzyRules............................. 467
21.2FuzzyInferencing.............................. 468
21.2.1 Fuzzification ............................ 469
21.2.2 Inferencing ............................. 470
21.2.3 Defuzzification ........................... 471
21.3Assignments................................. 472
22 Fuzzy Controllers 475
22.1ComponentsofFuzzyControllers..................... 475
22.2FuzzyControllerTypes .......................... 477
22.2.1 Table-BasedController....................... 477
22.2.2 MamdaniFuzzyController .................... 477
22.2.3 Takagi-SugenoController ..................... 478
22.3Assignments................................. 478
23 Rough Sets 481
23.1 Concept of Discernibility .......................... 482
23.2VaguenessinRoughSets.......................... 483
23.3UncertaintyinRoughSets......................... 484
23.4Assignments................................. 485
CONTENTS xvii
References 487
A Optimization Theory 551
A.1 BasicIngredientsofOptimizationProblems ............... 551
A.2 OptimizationProblemClassifications................... 552
A.3 OptimaTypes ............................... 553
A.4 OptimizationMethodClasses....................... 554
A.5 UnconstrainedOptimization........................ 555
A.5.1 ProblemDefinition......................... 555
A.5.2 Optimization Algorithms ..................... 555
A.5.3 ExampleBenchmarkProblems .................. 559
A.6 ConstrainedOptimization......................... 560
A.6.1 ProblemDefinition......................... 560
A.6.2 ConstraintHandlingMethods................... 561
A.6.3 ExampleBenchmarkProblems .................. 566
A.7 Multi-SolutionProblems.......................... 567
A.7.1 ProblemDefinition......................... 568
A.7.2 Niching Algorithm Categories . . ................. 568
A.7.3 ExampleBenchmarkProblems .................. 569
A.8 Multi-ObjectiveOptimization....................... 570
A.8.1 Multi-objectiveProblem...................... 570
A.8.2 WeightedAggregationMethods.................. 571
A.8.3 Pareto-Optimality ......................... 572
A.9 DynamicOptimizationProblems ..................... 575
A.9.1 Definition.............................. 576
A.9.2 DynamicEnvironmentTypes................... 576
A.9.3 ExampleBenchmarkProblems .................. 578
Index 581