混合整数规划问题算法研究资料.pptVIP

Branching Strategies * Branch-and-Bound Branching Strategies * Local Branching hamilton distance Given a feasible solution usually use as a heuristic Branching Strategies * Cut-and-Solve Cut-and-Solve BIP SP1 DP1 SP2 DP2 SP: sparse problem, UB DP: dense problem, LB Page* Disadvantage? When to stop? Thank you for your attention！ Page * Simple Genetic Algorithm initialize population; evaluate population; while (Termination Criteria Not Satisfied) { select parents for reproduction; perform recombination and mutation; evaluate population; } The GA Cycle of Reproduction reproduction population evaluation modification discard deleted members parents children modified children evaluated children Population Chromosomes could be: Bit strings (0101 ... 1100) Real numbers (43.2 -33.1 ... 0.0 89.2) Permutations of element (E11 E3 E7 ... E1 E15) Lists of rules (R1 R2 R3 ... R22 R23) Program elements (genetic programming) ... any data structure ... population Reproduction reproduction population parents children Parents are selected at random with selection chances biased in relation to chromosome evaluations. Chromosome Modification modification children Modifications are stochastically triggered Operator types are: Mutation Crossover (recombination) modified children Mutation: Local Modification Before: (1 0 1 1 0 1 1 0) After: (0 1 1 0 0 1 1 0) Causes movement in the search space(local or global) Restores lost information to the population Before: (1.38 -69.4 326.44 0.1) After: (1.38 -67.5 326.44 0.1) Crossover: Recombination P1 (0 1 1 0 1 0 0 0) P2 (1 1 0 1 1 0 1 0) * Crossover is a critical feature of genetic algorithms: It greatly accelerates search early in evolution of a population It leads to effective combination of schemata (subsolutions on different chromosomes) (0 1 0 0 1 0 0 0) C1 (1 1 1