### AN IMPROVED NICHE GENETIC ALGORITHM 评分

A simulated annealing based niche genetic algorithm (SANGA) has been presented to strength the optimization ability of niche genetic algorithm (NGA). The improved idea is to define niche formation using probability condition rather than simply distance condition. Individuals who only have close neig
speaking, the pseudo code of SaNGa is described as the e performance of four algor tFms in Schaffer follows writhe 3 Step 1. Initialization: initial genctic group(Go), population a o02 size (N), individuals to memorize (M), crossover probability (typical value PC=0.9), basal mutation probability(typical D01 alue pn=0.01), and other aided parameters Step2. Evolution: for current Gt-1, use crossover operation, mutation operation(for the ith individuals, Pmi the diversity of four al gort chaffer +algorithm 1 ) and selection operation to generate G Step3. Niche: for the N+ M individuals, compute their -algorithm 4 distance between their nearest neighbors, calculate Pi e-(Di-C)/(Di-C)to decide whether they are punished or not; 半半孝串掣中中k then sort these individuals by fitness, select the belter N individuals as Gt, memorize the better M individuals 10 Step4. Loop: if termination is satisfied, break, show output 引|cn and then stop else, back to Step 2. Figure 2. Four algorithms in schaffer function the performance of four algorithms in Bohachevsk III. SIMULATION algorithm 1 4.O In this part, four algorithms are tested in two optimization algorith problems to check their global optimization capability Algorithm I is current nGa based on penalty function; Algorithm 2 is NGa based on fitness sharing, the FSNGa; genera.ICh algor hm 1 Algorithm 3 is NGa based on deterministic crowding [4], the the diversit; of fo ur algorithms in 3ohachevsk3\ I algori. DONGA orithm 4 is the improved SaNGA. To eliminate the randomness of these algorithms the outcome is an average of 100 results. And the ga parts in them are the same, ++++4+4++++++|-++ including: Population size (N= 100); initial genetic group one-point cross over(P=0.9). one-point mutation(e</), relative fitness setting (fitness= lvalue -valuewors genera.ICn 0.01)and roulette wheel selection. Especially, the niche Figure 3. Four algorithms in Bohachevsky function distance(Euclidean distance) in NGA and FSNGa is set of entropy diversity, SANGA performs well as L =0.2, crowding factor in DCNGa is set as CF=3 In addition, entropy diversity are used to measure the C. Bohachevsky function(? diversity in genetic programming 5], and it is defined as MNy=x1+2x2-0.3c0s(3x1)+0cOS(4x2)+0.7 100≤x1,x2≤100 lo guopu) BEST SOLUTION: ymin =0,at (al,x2)=(0,0) While a partition pk is assumed as the probability of each Above are the definition and optimization of Bohachevsky different fitness value, it is easy to see entropy diversity function, and the following Fig 3 shows the performance of represents the information included in the genetic groups: four algorithms in it. SANGa has the best optimization ability Higher value means there are more unique individuals existing, (better outcome), and the entropy diversity of SANGA and lower value means there are more identical individuals remains high existing. Therefore, maximum value of entropy diversity for a Simulations prove that sanga performs better than current group which has 100 individuals(N=100)would be 2 NGA, FSNGA and DCNGA, showing better convergence B. Schaffer function /67 speed and optimization ability. In view of group diversity, sanga is likely to remain the highest (every individual is smx+x2)-05 MIN y=0.5+ unique). While sanga is not designed for some special 1+0.0001*(x2+x2)2) ble problems. it can be generally used in many fields, and 10≤x1,x2≤10 following is an example, its application in 0-1 knapsack BEST SOLUTION: ymin=0,at (ux2)=(0,0) problem Above are the definition and optimization of Schaffer APPLiCAtIoN function and Fig. 2 shows the performance of four algorithms in it. SANGa has the best convergence speed, and in the view A.0-I kn napsac the performarce of four ald 0-1 naps ack proble 0-1 knapsack problem [8 is well-known as a NP-hard problem, which is produced in real application problem such as project selection, portfolio, resource allocation, cargo loading and so on. As famous optimization algorithm, NGA is applied in it to get satisfied outcome. How to improve the performance of NGa is under study all the time. D B. mathematical model 0-1 knapsack problem aims at fill a knapsack, which has fixed limited capacity C. with several items, while each item has a weight Wi and profit Pi, to maximize the total profit Assuming there are n items in total and Xi (bool value)means whether the ith item is selected, its mathematical model can be set as: MAX ⅩV Figure 4. Four algorithms in 0-l knapsack problem(10 items) the performar ce of four algorithms in 0-1 knapsack problem 140 s7.)XW≤C 1000 +4++++++-+++ c. Genetic coding For 0-I knapsack problem, its input parameters are series of bool variables other than several continuous variables. To adapt this feature, the process of genetic coding is changed 产940 the ith gene chip directly represents whether the ith item is 一N〔具 宫92 select or not. For example, individual 1001110 means the lth 4th, 5th and 6th item are put into the knapsack, while the 2th, 3th and 7th item are not. That is to say, an individual directly represents [X,X2..Xn-1XnI. Death penalty is used to discern individuals which dont satisfy capacity restriction Other things are alike what have been done in the simulation part. Especially, the niche length(Hamming distance)in NGA and fsNga is set as 1/10 of the total item numbers Figure 5. Four algorithms in 0-1 knapsack problem(20 items) application. As for SanGa keeps effective in both D. Experiments simulations and application experiments, it can be seen Two experiments are taken to test SANGA and NGa, the saNga has great adaptability to the variety of optimization data and outcome comes from [91 oblems Experiment 1, 10 itemS, C=269 W={95,4,60,32,23,72,80,62,65,46} DISCUSSION AND CONCLUSION 1=155,10,47,5,4,50,8,61,85,87 This paper put forward a novel niche idea: Niche based on BEST SOLUTION: total value 295 simulated annealing. The core idea is to assume that any two Fig. 4 shows that SANGa quickly converges at the individuals may make up niche, while its probability is optimization in just about 6 to 8 generation, while NGa, nonlinearly inversely proportional to the distance between FSNGA and dONGa keep varying in less than 20 generation. these individuals, instead of employing simply distance It can be also seen that SANGa Steadily gives out best condition to judge niche formation. In simulations and 0-1 solutions knapsack problem, SANGA indeed shows superior, compared Experiment 2, 20 items, C=878 with fitness sharing, deterministic crowding and current niche W= genetic algorithm: Better convergence speed and optimization 492, 4,43,83,84,68,92, 82,6,44,32, 18,56,83,25,96,70,48,14,5,, ability, only a little extra time consuming. As a novel improved method, SANGa can be popularized in a wide field 44,46,90,72,9,40,75,35,8,5478,40.77,15,01,17,75,29,75,}. of optimization problems. BEST SOLUTION: total value 1024 REfERENCES In Fig. 5, the process is alike what it is in experiment 1. This means SANGa is strongly and swiftly adaptable to the [1] B. L. MILLER AND M J SHAW, "GENETIC ALGORITHMS WITH DYNAMIC changes of items. SANGA exhibit its superior in this NICHE SHARING FOR MULTIMODAL FUNCTION OPTIMIZATION. IN EVOLUTIONARY COMPUTATION, 1996., PROCEEDINGS OF IEEE 6Q. XIAOHONG AND L JUN,"A NOVEL ADAPTIVE PSO ALGORITHM ON INTERNATIONAL CONFERENCE ON, 1996, PP. 786-791 SCHAFFER'S F6 FUNCTION, IN HYBRID INTELLIGENT SYSTEMS. 2009. HIS 09. NINTH INTERNATIONAL CONFERENCE ON 2009. PP 94-98 [2]M. HUANG, N. LIU, AND X. LIANG, " AN IMPROVED NICHE GENETIC ALGORITHM, IN INTELLIGENT COMPUTING AND INTELLIGENT SYSTEMS, [7 L. MENGWEL, L. XIA, L. TAO, L. DAN, AND L. ZHENG,A GENE 2009C7S 2009. EEE INTERNATIONAL CONFERENCE ON 2009 Pp 291 EXPRESSION PROGRAMMING ALGORITHM FOR MULTIOBJECTIVE SITE- SEARCH PROBLEM, IN NATURAL COMPUTATION (ICNC), 2010 SIXTH INTERNATIONAL CONFERENCE ON. 2010. PP 14-18 [3R. A. RUTENBAR, SIMULATED ANNEALING ALGORITHMS: AN OVERVIEW, CIRCUITS AND DEVICES MAGAZINE, IEEE, VOL 5, Pp 19-26, [8 R MERKLE AND M. HELLMAN, HIDING INFORMATION AND SIGNATURES IN TRAPDOOR KNAPSACKS, INFORMATION THEORY, IEEE TRANSACTIONS ON,VOL.24,PP.525-530,1978 14Y. BO,"DETERMINISTIC CROWDING, RECOMBINATION ANDSELF SIMILARITY EVOLUTIONARY COMPUTATON, 2002. CEC 02 [] S. YUXIANG HONGWEN. AND Y. WEIMING SOLVE ZERO-ONE PROCEEDINGS OF THE 2002 CONGRESS ON. 2002. PP 1516-1521 KNAPSACK PROBLEM BY GREEDY GENETIC ALGORITHM. " IN INTELLIGENT SYSTEMS AND APPLICATIONS 2009. SA 2009 [5 E K. BURKE, S. GUSTAFSON, AND G. KENDALL, "DIVERSITY IN GENETIC INTERNATIONAL WORKSHOP ON 2009. PP, 1-4 PROGRAMMING: AN ANALY SIS OF MEASURES AND CORRELATION WITH FItNESS EVOLUTIONARY COMPUTATION. FEE TRANSACTIONS ON. vol 8 PP.47-62.2004

...展开详情

AN IMPROVED NICHE GENETIC ALGORITHM 立即下载
An improved algorithm for spectral 立即下载
An Improved Green Ratio Model 立即下载
An Improved method for MPPT 立即下载
An Improved Non-isolated LED Converter 立即下载
An Improved Canny Edge Detection Algorithm 立即下载
an improved illumination model for shaded display 立即下载
Masseter segmentation using an improved watershed algorithm 立即下载
An Improved Algorithm for Tor Circuit Scheduling 立即下载
An Improved Hierarchically Adaptive Distributed Fault Diagnosis 立即下载
code:AN IMPROVED NON-LOCAL DENOISING ALGORITHM 立即下载
An improved rotor speed estimation method of IPMSM 立即下载
An improved image mosaic based on Canny edge and an 18-dimensional descriptor 立即下载
An improved method for calculating the no-fit polygon 立即下载
An improved splash screen component for MFC(63KB) 立即下载
An improved edge detection algorithm for depth map inpainting 立即下载
An Improved Chirplet Transform and Its Application for Harmonics Detection.pdf 立即下载
An improved method which includes channel networks and convergence flow 立即下载
An improved algorithm for retrieving chlorophyll-a from MODIS imagery 立即下载
An improved genetic algorithm for the multi constrained 0–1 knapsack problem 立即下载