Begin with What is GA: GENETIC ALGORITHM
Hill climbing : multi-climbers to find a highest solution on global not local.
Select the best, discard the rest or Survival of the fittest.
Propagate Favorable > evolution
Nature = Genetic Algorithm
Population = Set of (candidate) Solution
Individual = (candidate) solution of problem
Chromosome = Encoded solution
Gene = Part of the encoded solution
Fitness = Quality of a solution
Crossover = Crossover
Mutation = Mutation
Allele ขอบเขตของ decision variable
Genotype = encode ลักษณะที่ปรากฎมา เช่น ตาสีดำใช้ B แทน GA [ data structure ]
Phenotype = ลักษณะที่ปรากฎมา เช่นตาสีฟ้า ผมสีทอง ของจริง โลกจริง เลขจำนวนจริง
Designing GA : How to build genotype that match problem phenotype
Initialize population by random in constrain on decision variable
-> Evaluate every chromosome get the fitness
-> Select (often 2) parents
-> Perform Crossover แลกเปลี่ยน ยีนส์พ่อ และ ยีนส์แม่
-> Perform Mutation ปรับปรุงยีน โดยแรนดอม
-> Evaluate the child chromosome get the fitness
-> Reinsert the child into the population
-> Terminate ? on condition
-> Return the best chromosome
Each chromosome called gene
Representation or encoding has great impacts on the GA operations.
Binary representation : 0/1
Integer representation : ex{0,1,2,3} denote {n, s, e, w }
Real-valued representation
Permutation representation : การเรียงสับเปลี่ยน ex: job shop scheduling จะจัดตารางเวลาอย่างไรให้ได้มากสุด ภายใต้เงื่อนไขที่มีเวลาอย่างจำกัด หรือ traveling salesperson problem
Fitness find the objective function
Random selection
Popotional
Roulette Wheel Selection (RWS) has high selection pressure ประชากรจะไม่กระจายตัวจะทำให้ Population diversity ต่ำ
Stochastic Universal Sampling (SUS) : เกิดการกระจายตัวดีกว่า RWS
Tournament Selection (การคัดเลือกโดยการแข่งขัน)
Parameter: k แบ่งกรุ๊ปแล้วเลือก the best ออกมา high selection pressure จะทำให้ เจอคำตอบเร็ว ซึ่งอาจทำให้เป็น local
So the end of the class today many about algorithm and how to selection how to define an objective
less pressure selection on random selection but in tournament you have to define parameter k so high or less is depending on it so this is all about my class to day have a nice day.
MySimpleDiary
ไม่มีความคิดเห็น:
แสดงความคิดเห็น