外文翻譯-- 量子遺傳算法的改進(jìn)

1、<p>　　2108單詞，3345漢字</p><p>　　畢業(yè)論文（設(shè)計(jì)）外文翻譯</p><p>　　題 目： </p><p>　　學(xué) 院： 數(shù)理與信息學(xué)院 </p><p>　　學(xué)生姓名：

2、 </p><p>　　專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級(jí)： </p><p>　　指導(dǎo)教師： </p>

3、<p>　　起止日期： 2014.11.28至2015.1.16 </p><p>　　2015年1月15日</p><p><b>　　<外文翻譯：原文></b></p><p><b>　　Pager1</b></p><p>　　An Impr

4、oved Quantum Genetic Algorithm</p><p>　　GUO Jian, SUN Li-juan, WANG Ru-chuan, YU Zhong-gen</p><p>　　College of Computer,Nanjing University of Posts and Telecommunications,</p><p>　　

5、Nanjing, China, guoj96@gmail.com</p><p>　　Abstract: Quantum genetic algorithm (QGA) is the combination between genetic algorithm and quantum computing. In this paper, a chromosome of the standard QGA is seen

6、 as a node and the chromosome population is regarded as a network. Then the reasons for the prematurity and the stagnation of the standard QGA are analyzed from the perspective of network structure. To solve the two prob

7、lems, an improved quantum genetic algorithm (IQGA) based on the small world theory is proposed. In IQGA, chromosome</p><p>　　1.INTRODUCTION</p><p>　　Genetic Algorithm (GA) is a random search alg

8、orithm based on the evolution theory of the survival of the fittest [1-5]. It has characteristics of parallelism and versatility. However, in practical applications, GA has a slow convergence speed, and is subject to a l

9、ocal optimal solution. Many improvements have been made. Among these, quantum genetic algorithm (QGA) proposed in the late nineties achieved significant results [6-13]. QGA introduced some thoughts of quantum computing i

10、nto GA, which g</p><p>　　QGA has shortcomings as well. As QGA chooses one optimal quantum chromosome each round to guide the evolution of all chromosomes, this approach undermines the diversity of the popula

11、tion, making the process subject to a local optimal solution. In this paper, analyses are given from the perspective of the structure of chromosome population, and defects are analyzed. To overcome the defects, an imp

12、roved quantum genetic algorithm (IQGA) based on the small world theory [14-16] is proposed. IQGA i</p><p>　　II. QUANTUM GENETIC ALGORITHM </p><p>　　QGA is the combination between GA and quantum

13、computing. It is based on the quantum vectors, representing chromosome by qubit coding, and updating chromosome by quantum rotation gate and quantum not gate. Eventually the optimal solution is supposed to be found out.

14、</p><p>　　A. Qubit encoding </p><p>　　Qubit is the smallest unit of information in QGA. A qubit may be in either ‘1’ or ‘0’state, or in any superposition of the both, i.e. a qubit may be |0>,

15、 |1>, or in the in-between state. Therefore, it can be expressed as: </p><p>　　|Ψ> = α|0> + β|1>, (1)</p><p>　　where α and β are two complex numbers satisfying |α|2 +|β|2 = 1.

16、|α|2 and |β|2 denote the probabilities of |0> and |1> respectively. </p><p>　　In QGA, qubits are used to represent a gene which expresses all the probable information instead of a set of definite infor

17、mation. And any operation carried out on this gene may exert influence on all possible information simultaneously. Furthermore, a chromosome can be encoded as:</p><p>　　where k denotes the number of qubits i

18、n each gene, while m is the number of genes in each chromosome. αxy and βxy (1≤x≤m,1≤y≤k) are two complex numbers satisfying |αxy|2 + |βxy|2 = 1. </p><p>　　B. Evolutionary operation </p><p>　　Q

19、uantum rotation gate is the implementation of evolution operation. It operates as: </p><p>　　where (αi,βi)T and (αi',βi')T are the i-th (1≤i≤mk) qubit of the pre-update and post-update chromosome r

20、espectively. θi is the rotation angle, whose value and direction can be adjusted by some strategies [7,10,11].</p><p>　　C. Workflow of QGA </p><p>　　The process of the standard QGA is detailed a

21、s follows: [10] </p><p>　　The population is initialized. All genes of chromosomes are initialized with (,) which means that a chromosome represents the linear superposition of all possible states with the sa

22、me probability. </p><p>　　All individuals are initially observed, and a group of solutions, p(t)={pt1,pt2,….ptn}, are obtained. ptj denotes the j-th solution of the population of the t-th round (namely the o

23、bservation result of the j-th individual). It is represented as an m-bit binary string, each bit of which is either 0 or 1. The observation process is to generate a random number in [0, 1]. If it is greater than the squa

24、re of the probability amplitude, the bit is set as 1, otherwise 0. Then each solution of the group </p><p>　　The algorithm enters into the stage of iteration. First, whether the condition to end the iteratio

25、n is met is determined. If met, then algorithm ends. Otherwise, all individuals of current population experience another observation, and the corresponding solutions and fitness are obtained. </p><p>　　Based

26、 on the current target value, the population is updated with quantum rotation gate, and a new population is generated. During the process of updating, individuals are observed and their fitness values are calculated. Com

27、pared with the fitness of the current target value, corresponding individual qubits of chromosomes are adjusted. </p><p>　　The optimal solution of current generation with the target value is compared. The be

28、tter one is chosen as the target of next evolution, and Step (3) recurs.</p><p>　　III. A NETWORK-LIKE ANALYSIS OF THE STANDARD QGA </p><p>　　If each quantum chromosome is seen as a node, then th

29、e population of the standard QGA is equivalent to a fully connected network of a high clustering coefficient and a short average path length, as shown in Fig. 1. This kind of network structure is favorable to information

30、 sharing among chromosomes, but to QGA, it undermines the diversity of individual chromosomes. The reason is that only one best chromosome is picked out as the evolution target of all chromosomes when updating the popula

31、tion. E</p><p>　　Conversely, if another topology structure, namely multi-group structure, is adopted, as shown in Fig. 2, the chromosomes are divided into some sub-groups and each of them sets up their own e

32、volution goals. All sub-groups are mutually independent. In this case, chromosomes are selected as the evolution targets, which is conducive to the diversity of the population. However, this new structure has a relativel

33、y great average path length, and sub-groups can not exchange information. So the algorithm</p><p>　　IV. SMALL WORLD THEORY </p><p>　　The phenomena of small world network are manifestations of c

34、lustering in the real networks. In 1967, professor Stanley Milgram of Harvard University found the phenomenon "Six Degrees of Separation" through the chain letters experiments, which was also known as the "

35、;small world". Based on this, Watts and Strogatz proposed a small world network model (WS model) in 1998, which reconnected every link in regular network at probability p [14]. Later, Newman and Watts improved the W

36、S model and advanced</p><p>　　V. AN IMPROVED QUANTUM GENETIC ALGORITHM </p><p>　　A. A bird-eye view </p><p>　　According to the analysis in Section 3, to converge quickly and avoid p

37、rematurity, the network of chromosome population ought to have the characteristics of both a relatively moderate clustering coefficient and a short average path. Therefore, the small world theory is introduced into QGA a

38、nd IQGA is proposed. The population network is transformed into a small world network. Consequently, the above problems are solved.</p><p>　　B. The design of IQGA</p><p>　　IQGA improves the stan

39、dard QGA mainly from the following aspects. (1) All chromosomes are divided into some sub-groups. </p><p>　　(2) After one round of evolution operation, each sub-group chooses the best chromosome as the ev

40、olution target of the next round. In this process, all chromosomes of this sub-group take part in the competition. So each sub-group is a fully connected network. Each chromosome connects other chromosomes through strong

41、 links. (3) In the implementation procedure of evolution operation, the chromosome does not simply choose its sub-group’s best chromosome as its evolution target, but selects other s</p><p>　　C. Workflow o

42、f IQGA </p><p>　　The process of IQGA is detailed as follows: (1) The population is divided into some sub-groups and all chromosomes are initialized. (2) The observation for every chromosome in all sub-

43、groups is implemented, and each solution of the sub-group is valued respectively. Then the best solution is saved as the target value of next evolution. (3) The algorithm enters into the stage of iteration. First, whe

44、ther the termination condition is met is determined. If met, then algorithm ends. Otherwis</p><p><b>　　.</b></p><p>　　(4) At a certain probability, the best chromosome from the sub-g

45、roup or other sub-groups is chosen as the evolution target for each chromosome. Then it is updated with quantum rotation gate. (5) For each sub-group, an optimal solution is found out again, and compared with the curre

46、nt target value. The better one is reserved, and Step (3) recurs.</p><p>　　VI. EXPERIMENTS AND TESTS </p><p>　　A. The design of experiments </p><p>　　In order to verify the validity

47、 of IQGA, three classical test functions are used for experiments. Comparative tests with the standard QGA are carried out. </p><p>　　These three functions are:</p><p>　　(1) Rastrigrin’ Function

48、</p><p>　　with the optimal solution: f1 (0, 0, …, 0) = 0;</p><p>　　(2) Griewank’ Function </p><p>　　with the optimal solution: f2 (0, 0, …, 0) = 0;</p><p>　　(3) Ackley’

49、 Function</p><p>　　xi∈[-32，32]</p><p>　　with the optimal solution: f3 (0, 0, …, 0) = 0. IQGA and QGA were realized with the C++ language under the Windows XP environment. The total number of

50、chromosomes was 200 and the time of iterations was 2000. In IQGA, the population was divided into 20 sub-groups. Two experiments were conducted. The effect of the weak link probability p to IQGA was tested in Experime

51、nt 1 and the performance of the two algorithms was compared in Experiment 2.</p><p>　　B. Results and analysis</p><p>　　1) Experiment 1</p><p>　　The value of p was set to 0, 0.1, 0.2

52、 …1. According to each value, each function was tested 10 times. Then the averages were calculated. The outcomes are shown from Fig. 5 to 7. </p><p>　　The above three figures show that if p is small, the pro

53、bability of sub-groups’ learning from each other will be slim and the degree of sharing information will be low. So the population stagnates early. When the p value ranges between 0.6 and 0.8, information is shared adequ

54、ately, and solutions IQGA obtained are better. Therefore, in the following experiments, the p value is set to 0.7.</p><p>　　2) Experiment 2 Each function was tested 20 times with IQGA and QGA respectively

55、. Table 1 shows the average of solutions of 20 times. Table 2 shows the comparison of optimal solutions gained by two algorithms. It is found that solutions obtained by IQGA are always better than those obtained by QGA,

56、especially those of f3. Evolution courses of optimal solutions to each function are shown from Fig. 8 to 10. Judged from the figures, solutions gained by QGA evolve faster than by IQGA at the in</p><p>　　

57、VII. CONCLUSION</p><p>　　The population structure has a great impact on the performance of the algorithm. And shortcomings of the standard QGA originate in its structural flaws. After the introduction of the

58、 NW model, the new population structure has a relatively modest clustering coefficient and a short average path length, which is helpful for the diversity of population as well as the exchange of information. Therefore t

59、he performance of IQGA is greatly improved. </p><p><b>　　<外文翻譯：譯文></b></p><p><b>　　量子遺傳算法的改進(jìn)</b></p><p>　　郭建，孫麗娟，王茹川，于忠根</p><p>　　南京郵電大學(xué)計(jì)算

60、機(jī)學(xué)院</p><p>　　摘要：量子遺傳算法（QGA）是結(jié)合遺傳算法和量子計(jì)算。在本文中，量子遺傳的染色體被視為一個(gè)節(jié)點(diǎn)和染色體種群被認(rèn)為是一個(gè)網(wǎng)絡(luò)。然后，從網(wǎng)絡(luò)結(jié)構(gòu)的角度分析得出的兩個(gè)原因是量子遺傳的早熟與停滯。為了解決這兩個(gè)問題,提出了一種基于小世界理論的改進(jìn)的量子遺傳算法(IQGA)。在改進(jìn)的量子遺傳算法中,基于量子比特的染色體編碼被分為一些子群體和NW網(wǎng)絡(luò)模型被引入種群結(jié)構(gòu)。當(dāng)更新染色體時(shí)，把一個(gè)最優(yōu)染

61、色體位置作為其他群體進(jìn)化時(shí)基于一定概率所選擇的的目標(biāo)。新的染色體種群網(wǎng)絡(luò)結(jié)構(gòu)有相對(duì)溫和的聚類系數(shù)和有利于個(gè)體染色體的多樣性。測(cè)試三個(gè)經(jīng)典函數(shù)證明IQGA的有效性和優(yōu)越性。</p><p>　　關(guān)鍵詞：改進(jìn)量子遺傳算法;量子遺傳算法;NW網(wǎng)絡(luò)模型;小世界</p><p><b>　　1.引言</b></p><p>　　遺傳算法(GA)是一種基于

62、進(jìn)化理論適者生存[1 - 5]的隨機(jī)搜索算法。他具有并行性和通用性的特點(diǎn)。然而,在實(shí)際應(yīng)用中,遺傳算法會(huì)有收斂速度慢、陷入局部最優(yōu)解的現(xiàn)象。為此做了很多改進(jìn)。其中,在90年代提出的量子遺傳算法(QGA)[6-13]有了很大進(jìn)步。量子遺傳算法實(shí)現(xiàn)了將量子計(jì)算思想運(yùn)用到遺傳算法,大大提高了并行遺傳操作和加速收斂的過程。</p><p>　　量子遺傳算法同樣也有缺點(diǎn)。因?yàn)樵诿看辛孔舆z傳算法是選擇一個(gè)最佳的量子染色體指

63、導(dǎo)所有染色體的進(jìn)化,這種方法破壞了種群的多樣性,使結(jié)果趨向局部最優(yōu)解。</p><p>　　本文中，從染色體種群的結(jié)構(gòu)的角度來和缺陷進(jìn)行了分析。為了克服這種缺點(diǎn),一種基于小世界理論[14-16]的改進(jìn)的量子遺傳算法(IQGA)被提出。IQGA介紹了NW網(wǎng)絡(luò)模型[15]和改善種群結(jié)構(gòu),因此種群具有多樣性。IQGA的有效性和優(yōu)越性通過典型函數(shù)的測(cè)試演示了。</p><p><b>　

64、　2.量子遺傳算法</b></p><p>　　量子遺傳算法是結(jié)合遺傳算法和量子計(jì)算。它是基于量子向量的量子位編碼的染色體,染色體的更新通過量子門旋轉(zhuǎn)門和量子非門。最終找到期望的最優(yōu)解。</p><p><b>　　2.1 量子位編碼</b></p><p>　　在量子遺傳中量子位是信息的最小單位。量子位可以在‘1’或‘0’態(tài),或任

65、何態(tài)的疊加,即量子位可以|0>,|1>,或是他們的任何疊加態(tài)。因此,它可以表示為:</p><p>　　|Ψ> =α|0 >+β|1 >, (1)</p><p>　　α和β兩個(gè)復(fù)數(shù)滿足|α2| + |β2|= 1 |α2|和|β2|分別表示|0>和|1>的概率。</p><p>　　在量子遺傳算

66、法中,量子比特位用于表示一個(gè)基因可能表達(dá)的所有可能的信息,而不是一系列確定的信息。對(duì)這種基因的任何操可能對(duì)所有可能的信息同時(shí)施加影響。此外,可以將染色體編碼為:</p><p>　　k代表每個(gè)基因在染色體上的位置,而m是每個(gè)染色體的基因數(shù)量。αxy和βxy(1≤x≤m, 1≤y≤k)是兩個(gè)復(fù)數(shù)滿足|αxy|2 + |βxy|2 = 1。</p><p><b>　　2.2進(jìn)化操作

67、</b></p><p>　　進(jìn)化操作是量子旋轉(zhuǎn)門實(shí)現(xiàn)的。它是:</p><p>　　(αiβi)T和(αi ',βi ')T是第i個(gè)(1≤≤mk)分別更新前和更新后處理染色體的量子位。θi旋轉(zhuǎn)角,其大小和方向可以通過調(diào)節(jié)對(duì)策[7,10,11]來改變。</p><p>　　2.3 工作流的實(shí)現(xiàn)</p><p>　　

68、量子遺傳算法詳細(xì)運(yùn)行過程如下[10]: </p><p>　　(1)初始化種群。所有基因的染色體是初始化(,)這意味著一個(gè)染色體所表達(dá)的是其全部可能狀態(tài)的等概率疊加；</p><p>　　(2)最初觀察所有的個(gè)體,一組解集為p(t)= { pt1 pt2,…。得到了ptn },。ptj表示第j個(gè)染色體的第t代 (即第j個(gè)染色體的觀察結(jié)果)。表示為一個(gè)二進(jìn)制字符串,每個(gè)位是0或1。通過生成一

69、個(gè)在0~1的隨機(jī)數(shù)。如果它是大于概率振幅的平方,位設(shè)置為1,否則為0。然后算出每個(gè)方案的值,記錄最優(yōu)個(gè)體和對(duì)應(yīng)的適應(yīng)度作為下一代進(jìn)化的目標(biāo)；</p><p>　　(3)進(jìn)入算法的迭代階段。首先,結(jié)束迭代的條件是否得到滿足。如果滿足,那么算法結(jié)束。否則,對(duì)種群中的每個(gè)個(gè)體實(shí)施一次測(cè)量，得到相應(yīng)的確定解，對(duì)各確定解進(jìn)行適應(yīng)度評(píng)估</p><p>　　(4)基于當(dāng)前最優(yōu)個(gè)體,利用量子旋轉(zhuǎn)門對(duì)個(gè)體

70、實(shí)施調(diào)整，得到新的種群。在更新的過程中,計(jì)算種群個(gè)體適應(yīng)度。與當(dāng)前目標(biāo)的適應(yīng)度相比,相應(yīng)調(diào)整個(gè)別量子位的染色體；</p><p>　　(5)將前一代的最優(yōu)解與現(xiàn)在的比較。更好的選擇一個(gè)作為下一代進(jìn)化的目標(biāo),返回步驟(3)；</p><p>　　3.網(wǎng)絡(luò)似乎分析標(biāo)準(zhǔn)的實(shí)現(xiàn)</p><p>　　如果每個(gè)量子染色體被視為一個(gè)節(jié)點(diǎn),然后量子遺傳算法標(biāo)準(zhǔn)的種群相當(dāng)于一個(gè)完全連

71、接網(wǎng)絡(luò)的聚類系數(shù)和平均路徑長(zhǎng)度短,如圖1所示。這種網(wǎng)絡(luò)結(jié)構(gòu)有利于染色體的信息共享,但是對(duì)于量子遺傳算法,它削弱了個(gè)體染色體的多樣性。原因是只有一個(gè)最好的染色體作為所有染色體的進(jìn)化更新的目標(biāo)。每個(gè)染色體進(jìn)化按照最好的。結(jié)果,算法局部最優(yōu)和不成熟的現(xiàn)象出現(xiàn),即整個(gè)種群收斂到第一個(gè)近似最優(yōu)解。</p><p>　　相反,如果采用另一個(gè)拓?fù)浣Y(jié)構(gòu),即多群結(jié)構(gòu)。如圖2所示,染色體分為成一些子群體,他們每個(gè)人都建立自己的進(jìn)化目

72、標(biāo)。所有的群體是相互獨(dú)立的。在這種情況下,染色體是選為進(jìn)化的目標(biāo),這有利于種群的多樣性。然而,這種新結(jié)構(gòu)相對(duì)平均路徑較長(zhǎng)和群體不能交換信息。因此該算法缺乏適當(dāng)?shù)男畔砀路N群和收斂緩慢。因此,上述兩種結(jié)構(gòu)都不適合量子遺傳算法。</p><p><b>　　4.小世界理論</b></p><p>　　小世界網(wǎng)絡(luò)的現(xiàn)象是在現(xiàn)實(shí)網(wǎng)絡(luò)的集群表現(xiàn)。1967年,哈佛大學(xué)的教授St

73、anley Milgram通過連鎖信實(shí)驗(yàn)，發(fā)現(xiàn)“六度分離”現(xiàn)象,也被稱為“小世界”。在此基礎(chǔ)上,1998年Watts 和Strogatz 提出了一個(gè)小世界網(wǎng)絡(luò)模型(WS模型) [14]，它以概率p重新連接固定網(wǎng)絡(luò)中的每一個(gè)環(huán)節(jié)。之后, Newman 和Watts改進(jìn)WS模型和提出了先進(jìn)的NW網(wǎng)絡(luò)模型[15]。模型增加了任意選擇兩個(gè)長(zhǎng)距離節(jié)點(diǎn)連接,并保留原始連接。這個(gè)過程如圖3所示。</p><p>　　

74、原始連接在網(wǎng)絡(luò)被稱為緊密聯(lián)系，添加連接被稱為無力連接。研究表明,無力連接很難改變聚類系數(shù),但他們可以大大減少網(wǎng)絡(luò)的平均路徑長(zhǎng)度。</p><p>　　5.一種改進(jìn)的量子遺傳算法 </p><p><b>　　5.1. 鳥眼視圖</b></p><p>　　在根據(jù)第三節(jié)的分析，為了迅速收斂和避免早熟，染色體種群網(wǎng)絡(luò)應(yīng)該有相對(duì)溫和的聚類系數(shù)和平均路

75、徑短的特點(diǎn)。因此，將小世界理論引用到量子遺傳算法提出了IQGA。種群網(wǎng)絡(luò)轉(zhuǎn)化為一個(gè)小世界網(wǎng)絡(luò)。因此,上述問題得到解決。</p><p>　　5.2 IQGA的設(shè)計(jì)</p><p>　　IQGA主要通過以下幾方面改進(jìn)傳統(tǒng)量子遺傳算法。</p><p>　　(1)所有染色體分成一些子群體。</p><p>　　(2)之后的一輪進(jìn)化操作,每一個(gè)子群

76、體中選擇最好的染色體作為下一輪的進(jìn)化的目標(biāo)。在這個(gè)過程中,所有染色體的子群體參加競(jìng)爭(zhēng)。所以每個(gè)子群是一個(gè)完全連接的網(wǎng)絡(luò)。每個(gè)染色體通過強(qiáng)連接連接其他染色體。(3) 進(jìn)化操作的實(shí)現(xiàn)過程,染色體不是簡(jiǎn)單地選擇其子種群最好的染色體作為進(jìn)化目標(biāo),而是有一定的概率選擇其他群體最好的染色體。所以在這個(gè)染色體和其他群體之間的無力連接被改變。群體之間的信息交換和收斂速度都有提高。IQGA的種群結(jié)構(gòu)如圖4所示。</p><p>　

77、　5.3. 工作流的IQGA</p><p>　　IQGA的詳細(xì)工作過程如下:</p><p>　　(1)種群被分為一些子群體和所有染色體都初始化。</p><p>　　(2)觀察每一個(gè)在子種群的的實(shí)現(xiàn)的染色體,分別計(jì)算子群的每個(gè)適應(yīng)度值。然后保存最好的個(gè)體為下一代進(jìn)化的目標(biāo)。</p><p>　　(3)進(jìn)入算法的迭代階段，首先,結(jié)束迭代的條

78、件是否得到滿足。如果滿足,那么算法結(jié)束。否則,對(duì)種群中的每個(gè)個(gè)體實(shí)施一次測(cè)量，得到相應(yīng)的確定解，對(duì)各確定解進(jìn)行適應(yīng)度評(píng)估。</p><p>　　(4)基于當(dāng)前最優(yōu)個(gè)體,利用量子旋轉(zhuǎn)門對(duì)個(gè)體實(shí)施調(diào)整，得到新的種群。在更新的過程中,計(jì)算種群個(gè)體適應(yīng)度。與當(dāng)前目標(biāo)的適應(yīng)度相比,相應(yīng)調(diào)整個(gè)別量子位的染色體。</p><p>　　(5)將前一代的最優(yōu)解與現(xiàn)在的比較。更好的選擇一個(gè)作為下一代進(jìn)化的目標(biāo)

79、,返回步驟(3)。</p><p><b>　　6、實(shí)驗(yàn)和測(cè)試</b></p><p><b>　　6.1．實(shí)驗(yàn)的設(shè)計(jì)</b></p><p>　　為了驗(yàn)證的有效性IQGA,將三個(gè)經(jīng)典測(cè)試函數(shù)用于實(shí)驗(yàn)。對(duì)比實(shí)驗(yàn)與標(biāo)準(zhǔn)QGA的結(jié)果得出結(jié)論。</p><p><b>　　這三個(gè)函數(shù)是:<

80、/b></p><p>　　(1)Rastrigrin”函數(shù)</p><p>　　最優(yōu)解： f1 (0, 0, …, 0) = 0;</p><p>　　(2) Griewank函數(shù) </p><p>　　最優(yōu)解： f2 (0, 0, …, 0) = 0;</p><p>　　(3) Ackley函數(shù)</p

81、><p>　　xi∈[-32，32]</p><p>　　最優(yōu)解：f3 (0, 0, …, 0) = 0;</p><p>　　IQGA和QGA在Windows XP環(huán)境下用c++語(yǔ)言實(shí)現(xiàn)。染色體的總數(shù)是200和迭代的次數(shù)是2000次。在IQGA中,種群分為20組。</p><p>　　進(jìn)行了兩個(gè)實(shí)驗(yàn)。以概率p對(duì)IQGA無力連接測(cè)試的性能在實(shí)驗(yàn)1

82、進(jìn)行測(cè)試和實(shí)驗(yàn)2中是對(duì)兩個(gè)算法進(jìn)行了比較。</p><p><b>　　6.2結(jié)果與分析</b></p><p>　　6.2.1. 實(shí)驗(yàn)1 </p><p>　　p的值被設(shè)置為0,0.1,0.2…1。根據(jù)這個(gè)值,每個(gè)函數(shù)測(cè)試10次。然后平均計(jì)算。結(jié)果如圖5 至7所示。</p><p>　　有上面的三幅圖表明,如果p很小,

83、小組互相學(xué)習(xí)的概率很小和信息共享的程度很低。因此,種群停滯。當(dāng)p值范圍在0.6和0.8之間,信息充分共享,IQGA獲得更好的解。因此,在接下來的實(shí)驗(yàn)中,p值設(shè)置為0.7。</p><p><b>　　6.3.2 實(shí)驗(yàn)2</b></p><p>　　每個(gè)函數(shù)測(cè)試分別用IQGA和QGA測(cè)試20次。表1顯示了測(cè)試20次的平均解。表2顯示了兩種算法的最優(yōu)解的比較。發(fā)現(xiàn)解決方案

84、通過IQGA總是比那些通過QGA的好,特別是f3。</p><p>　　每個(gè)函數(shù)的進(jìn)化的最優(yōu)方案,顯示在圖8到10。從這個(gè)數(shù)據(jù)，通過QGA的方法比IQGA也要快,在初始階段。但他們通常經(jīng)過400輪停止。ＱＧＡ?xí)羧氩怀墒斓臓顟B(tài)和停滯不前的狀態(tài)。相比之下,通過IQGA解決方案發(fā)展速度仍然緩慢甚至經(jīng)過700輪后,因此好多了。</p><p><b>　　7、結(jié)論</b>&