CS计算机代考程序代写 data mining assembly algorithm Metaphor

Metaphor
 Geneticalgorithmisasearchmethodthatisinspiredbythe process of natural evolution.
 Itislikeotherlocalsearchmethods,butthemaindifferenceis population‐based search, where solutions with higher fitness in the population have better chance to survive and produce offspring.
NATURAL EVOLUTION
PROBLEM SOLVING
Individual Fitness Environment Generation
Candidate Solution Quality Problem Iteration

Algorithm Procedure
But first we need to know how to represent a solution!

Designing a Representation
 Usuallyanindividual(phenotype)ingeneticalgorithmis represented as a genotype.
 Therearemanywaystodothisandthewaywechoosemust be relevant to the problem that we are solving.
 Whenchoosingarepresentation,weneedtobearinmindhow the genotypes will be evaluated and what the genetic operators (i.e. crossover and mutation) might be.

Binary Representation
 Binaryencodingisacommonlyusedrepresentation.  Whatcanthefollowing8‐bitgenotyperepresent?
CHROMOSOME
Phenotype: • Integer
GENE
• Real Number • Subset
• …

Binary Representation for integer numbers
Genotype: Phenotype: = 163
1*27 + 0*26 + 1*25 + 0*24 + 0*23 + 0*22 + 1*21 + 1*20 = 128 + 32 + 2 + 1 = 163

Binary Representation for real numbers
 Example:minimise variable is
􏰀,wherethedomainofthe
Genotype:
Phenotype: = 14.0059
.

Other Representations
 Realnumberrepresentation:directlyuserealnumbersto represent solutions; in this case there is no difference between genotype and phenotype.
 For the above example of minimising 􏰁􏰂􏰃􏰄 􏰅 􏰃 􏰆 4 􏰀, 􏰃 ∈ 􏰇2.5, 20.5􏰈, we can directly consider the real number of 􏰃 in genetic algorithm (as long as we can come up with variation operators for it).
 Ordinalrepresentation:usepermutationstorepresentsolutions; suitable for ordering/sequencing problems
 Example: Travelling Salesman Problems (TSPs), every city gets a unique number from 1 to n. A solution can be (5, 1, 2, 3, 4).
 Need special variation operators to make sure solutions stay valid permutations.

Component – Population Initialisation

Population Initialisation
 Inmostcases,sampleuniformly from the search space, e.g.:
Example: minimise 􏰁􏰂􏰃􏰄 􏰅 􏰃􏰆1 􏰀,wherethedomainof
 Binary representations: 0 or 1 with probability 0.5;
the variable 􏰃 is [0, 3]. 1011
 Real‐valued representations: uniformly on a given interval.
 Seedthepopulationwithexisting results (e.g. from some approximation methods in TSP); but we may avoid premature convergence.
0110 0001 1010

Population Evaluation
 Evaluate individuals (based on the objective function) and assign fitness to them.
Example: minimise 􏰁􏰂􏰃􏰄 􏰅
􏰃 􏰆 1 􏰀, where the domain of
 Individuals’ fitness can be their objective values for single‐objective problems.
the variable 􏰃 is [0, 3]. 1011
 For multi‐objective problems, one needs to design very different fitness assignment methods.
0110 0001 1 0 1 0
 Can be expensive in some real‐world scenarios like in black‐box simulator e.g., complex software systems and car engine calibration.
Solution1: 􏰃􏰉 􏰅 2.2, 􏰁 􏰃􏰉 Solution2: 􏰃􏰀 􏰅 1.2, 􏰁 􏰃􏰀 Solution3: 􏰃􏰊 􏰅 0.2, 􏰁 􏰃􏰊 Solution4: 􏰃􏰋 􏰅 2.0 􏰁 􏰃􏰋
􏰅 1.44 􏰅 0.04 􏰅 0.64
􏰅 1.0

Selection
 Selection(ormatingselection)istoselectsolutionsfromthe population to produce offspring based on their fitness.
 Thebasicprincipleisthatwewanttogivebettersolutionshigher chance to produce offspring, but also to give less good solutions at lest some chance (they may include some useful genes).
 Roulettewheelselection:probability of solution 􏰌 being selected is
􏰌
,
where 􏰍􏰎􏰏_􏰁􏰐􏰑 is the sum of the fitness of all solutions. For maximisation problem, the fitness of a solution can be its objective value; for minimisation problem the fitness can be 1 􏰆 􏰒􏰓􏰔􏰏􏰂􏰁􏰂􏰃􏰌􏰄􏰄 for example.

Selection
 Selection(ormatingselection)istoselectsolutionsfromthe population to produce offspring based on their fitness.
 Thebasicprincipleisthatwewanttogivebettersolutionshigher chance to produce offspring, but also to give less good solutions at lest some chance (they may include some useful genes).
 Tournamentselection:Pick
solutions (e.g., ) from
the population, select the best
one for mating; repeat this
times, so solutions are in M mating pool.
ELFD
G
Population
B H ACMN
C
F
Contestants (k=3)
F
Winner

Crossover
 Crossover(alsocalledrecombination)isageneticoperatorusedto combine the genetic information of two parents to generate new offspring. It is usually applied with a high probability, e.g. 􏰕 .
 Therearemanycrossoveroperators:
Parents
0110 0001
Single-point crossover
0 1 1 1 0000
Offspring
 
Binary representation: single‐point crossover, k‐point crossover, uniform crossover
Real‐valued representation: single‐point crossover, simplex crossover, simulated binary crossover

Mutation
 Mutationisageneticoperatorusedtomaintaingeneticdiversity by altering one or more gene values in a chromosome. It is usually applied with a very low probability, e.g. 􏰖 .
 Itshouldbedesignedinsuchawaythateverypartofthesearch space can be reached.
 Therearedifferentmutationoperators:
Parent
Bit flip
0 1 1 1 mutation 0 1 0 1 Offspring
 
Binary representation: bit flip mutation
Real‐valued representation: Gaussian mutation, polynomial mutation

Population Updating
 Populationupdating(orenvironmentalselection)istoupdatethe old population by newly‐produced solutions.
 Elitism:bestsolutionshouldalwaysbekept.
 Therearedifferentmethods(esp.formulti‐objectiveoptimisation),
one of which is purely based on fitness.
Old population 􏰁􏰃􏰉 􏰅1.44 1 0 1 1
Newly produced individuals
New population
􏰁􏰃􏰀 􏰅0.04 0 1 1 0 􏰁􏰃􏰊 􏰅0.64 0 0 0 1 􏰁􏰃􏰋 􏰅1.0 1 0 1 0
􏰁􏰃􏰘 􏰅1.0 0 0 0 0 􏰁􏰃􏰙 􏰅3.24 1 1 1 0 􏰁􏰃􏰚 􏰅0.36
􏰁􏰃􏰗 􏰅0.0 0 1 0 1
0 1 0 1
0 1 1 0 0 0 1 0 0010 0001

Stopping Criterion
 Optimumisreached.
 Givenamountoftime,ormaximumgenerations.
 Aftersomegenerations,thereisnoimprovementonthe population’s quality.
 Donotdrawanyconclusionfromasinglerundueto randomness nature of genetic algorithm (initialisation, selection, crossover and mutation):
 Runthealgorithmasufficientnumberofindependent times, e.g. 30 runs.
 Usestatisticalresultstoevaluatethealgorithm,e.g. mean and standard deviation.

Applications
 Itcanbeappliedtovariousproblems,wheretheoptimal solution cannot be derived analytically (e.g. by math programming methods) or be obtained in reasonable time (e.g. by exhaustive search like DFS and A*).
 Domains:
 Numerical, Combinatorial Optimisation
 System Modeling and Identification
 Planning and Control
 Engineering Design
 Data Mining
 Machine Learning
 Artificial Life

Applications
 Softwareengineering
 Schedulingincouldcomputing
 Automatedproductdisassembly
 Emergencyreliefsupplydistribution
 Creatingunexpectedpatternsinart
 Neuralarchitecturesearch
 Reinforcementlearningforvideogames