下载  >  网络技术  >  其它  > AN IMPROVED NICHE GENETIC ALGORITHM

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

...展开详情
所需积分/C币:3 上传时间:2014-04-23 资源大小:237KB
举报 举报 收藏 收藏
分享 分享
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

立即下载
An improved algorithm for spectral

An improved algorithm for spectral emissivity measurements at low temperatures based on the multi-temperature calibration method

立即下载
An Improved Green Ratio Model

描绘控制论的东西,平台是交通信号优化,大家看一看啊瞧一瞧多支持,烦的一笔字数够了吧

立即下载
An Improved method for MPPT

for solar system MPPT

立即下载
An Improved Non-isolated LED Converter

An Improved Non-isolated LED Converter with Power Factor Correction and Average Current Mode Control

立即下载
An Improved Canny Edge Detection Algorithm

canny边缘检测改进论文 介绍可一种canny边缘检测的改进方法

立即下载
an improved illumination model for shaded display

To accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this information is stor

立即下载
Masseter segmentation using an improved watershed algorithm

关于医学分水岭分割的一篇国外论文 写的比较细

立即下载
An Improved Algorithm for Tor Circuit Scheduling

Tor is a popular anonymity-preserving network, consisting of routers run by volunteers all around the world. It pro- tects Internet users' privacy by relaying their network trac through a series of routers, thus concealing the linkage be- tween the sender and the recipient. Despite the advantage of

立即下载
An Improved Hierarchically Adaptive Distributed Fault Diagnosis

The purpose of fault diagnosis in mobile ad hoc network is to have each fault-free node to determine the state of all nodes in the system. This paper proposes a fault diagnosis algorithm based on the approach proposed in [1] for diagnosing nodes in mobile ad hoc network. The proposed diagnosis algor

立即下载
code:AN IMPROVED NON-LOCAL DENOISING ALGORITHM

AN IMPROVED NON-LOCAL DENOISING ALGORITHM,NON-LOCAL DENOISING ALGORITHM code

立即下载
An improved rotor speed estimation method of IPMSM

Abstract-In order to estimate the speed fluctuation band of interior permanent magnet synchronous motor (IPMSM) under speed sensorless control with cyclic fluctuating load accurately, an improved rotor speed estimation method is proposed. A rotor flux oriented vector control with conventional model

立即下载
An improved image mosaic based on Canny edge and an 18-dimensional descriptor

To gain the wide view angle and high resolution image stitched by the sequence images overlapped in the same scene, this paper proposes a new image mosaic method of combining the improved SIFT algo- rithm with Canny feature edge detection based on the traditional scale invariant feature transform (S

立即下载
An improved method for calculating the no-fit polygon

An improved method for calculating the no-fit polygon Hamish T. Dean∗,Yiliu Tu, John F. Raffensperger 200 Armagh Street, P.O. Box 13-761, Christchurch, New Zealand

立即下载
An improved splash screen component for MFC(63KB)

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 Chirplet Transform and Its Application for Harmonics Detection

立即下载
An improved method which includes channel networks and convergence flow

The LS-TOOL algorithm can automatically calculate slope length, slope steepness, L factor, S factor, and LS factors, providing the results as ASCII files which can be easily used in some GIS software. This study is an important step forward in conducting accurate large-scale erosion evaluation.

立即下载
An improved algorithm for retrieving chlorophyll-a from MODIS imagery

In this study, an improved MODIS ocean chlorophyll-a (chla) 3 model (IOC3M) algorithm was developed as a substitute for the MODIS global chla concentration estimation algorithm, OC3M, to estimate chla concentrations in waters with high suspended sediment concentrations (SSC), such as the Yellow Rive

立即下载
An improved genetic algorithm for the multi constrained 0–1 knapsack problem

An improved genetic algorithm for the multi constrained 0–1 knapsack problem 使用遗传算法解决多维背包问题。

立即下载