Friday, 2020-02-28 BioInfo Pakistan
Section categories
 Related Subjects [38]This category includes brief overview of all related subjects. Defining BioInformatics [7]In this section we tried to briefly explain what bioinformatics is ? Unviersities [30]This contains information about universities that are offering bioinformatics degree programs. Resources [24]Contains information about bioinformatics resources including databases, tools and techniques. Algorithms [31]This category includes some of the basic algorithms that are usually used by bioinformaticians.
 Our poll Pakistani Student Yes No Total of answers: 0
 Chat Box Only authorized users can post messages
 Statistics Total online: 1 Guests: 1 Users: 0
Home » 2011 » August » 22 » Genetic Algorithms
10:25 PM
Genetic Algorithms

 Genetic AlgorithmsPage: 2 31. Description:   A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.2. Steps:EncodingFitness EvaluationReproductionSurvivor Selection3. Encoding:Design alternative à individual (chromosome)Single design choice à geneDesign objectives à fitnessExample: ProblemSchedule n jobs on m processors such that the maximum span is minimized.Design Alternative: job i ( i=1,2,…n) is assigned to processor j  (j=1,2,…,m)Individual: A n-vector x such that xi = 1, …,or mDesign objective: minimize the maximal spanFitness: the maximal span for each processor4. Reproduction:Reproduction operatorsCrossoverMutationCrossoverTwo parents produce two offspringThere is a chance that the chromosomes of the two parents are copied unmodified as offspringThere is a chance that the chromosomes of the two parents are randomly recombined (crossover) to form offspringGenerally the chance of crossover is between 0.6 and 1.0MutationThere is a chance that a gene of a child is changed randomlyGenerally the chance of mutation is low (e.g. 0.001)5. Reproduction Operators:CrossoverGenerating offspring from two selected parentsSingle point crossoverTwo point crossover (Multi point crossover)Uniform crossoverRandomly one position in the chromosomes is chosenChild 1 is head of chromosome of parent 1 with tail of chromosome of parent 2Child 2 is head of 2 with tail of 1Single point crossoverTwo point crossover (Multi point crossover)One-point crossover - NatureTwo-point crossoverUniform crossoverA random mask is generatedThe mask determines which bits are copied from one parent and which from the other parentBit density in mask determines how much material is taken from the other parent (takeover parameter)Is uniform crossover better than single crossover point?Trade off betweenExploration: introduction of new combination of featuresExploitation: keep the good features in the existing solutionDepending on coding, simple crossovers can have high chance to produce illegal offspring E.g. in TSP with simple binary or path coding, most offspring will be illegal because not all cities will be in the offspring and some cities will be there more than onceUniform crossover can often be modified to avoid this problemE.g. in TSP with simple path coding:Where mask is 1, copy cities from one parentWhere mask is 0, choose the remaining cities in the order of the other parentMutationGenerating new offspring from single parentMaintaining the diversity of the individualsCrossover can only explore the combinations of the current gene poolMutation can "generate” new genesControl Parameters: population size, crossover/mutation probabilityProblem specificIncrease population sizeIncrease diversity and computation time for each generationIncrease crossover probabilityIncrease the opportunity for recombination but also disruption of good combinationIncrease mutation probabilityCloser to randomly searchHelp to introduce new gene or reintroduce the lost geneVaries The Population:Usually using crossover operators to recombine the genes to generate the new population, then using mutation operators on the new populationPage: 2 3
Category: Algorithms | Views: 1556 | Added by: Ansari | Rating: 0.0/0