ga-translate.txt

GA sources code in C++

堚揱揑傾儖僑儕僘儉偺揔梡(Application of genetic algorithm)

廬棃偺惍悢寁夋栤戣偺夝朄偲偟偰丆楍嫇朄丆暘巬尷掕朄丆Gomory偺愗彍暯柺朄丆儔僌儔儞僕儏娚榓朄摍傗丆
偙傟傜偺僴僀僽儕僢僪壔偟偨庤朄偑棙梡偝傟偰偒偨丏偟偐偟側偑傜丆幚婯柾儗儀儖偺
栤戣偵懳偟偰偼丆慻崌偣悢偑朿戝偲側傞偨傔廬棃偺嵟揔壔庤朄偱偼丆寁嶼偑崲擄偲側傞丏偦偙偱杮尋媶偱
偼丆嬤擭慻崌偣嵟揔壔栤戣偵懳偟偰桳岠側庤朄偱偁傞堚揱揑傾儖僑儕僘儉偺揔梡傪帋傒傞丏偝傜偵丆帒尮
偺攝暘壜擻検偺惂尷傪梲偵埖偊傞傛偆偵丆夵椙傪壛偊偨堚揱揑傾儖僑儕僘儉偺庤朄傪揔梡偡傞丏

The technique that cut methods of the enumeration method, the offshoot limitation method, and 
Gomory, the Lagrange easing methods, and etc. these are made hybrid has been used as a method of 
a past integer plan problem. However, because the number of combinations becomes huge, the 
calculation becomes difficult for the problem at the real scale level in a past optimization 
technique. Then, the application of the genetic algorithm that is an effective technique is tried 
to the combination optimization problem in this research in recent years. In addition, the 
limitation of the amount to be able to distribute the resource does and the technique of the 
genetic algorithm that adds the improvement to the positive to treat is applied. 

堚揱揑傾儖僑儕僘儉偺榞慻傒偼丆1975擭Holland偵傛偭偰揔墳僔僗僥儉偺堦庬偲偟偰採埬偝傟偨.偦偺儊僇
僯僘儉偼丆僟乕僂傿儞偺帺慠搼懣偺棟榑偵婎慴傪偍偔惗暔偺恑壔夁掱傪柾曧偟偨岺妛揑儌僨儖偱偁傞.偡
側傢偪丆悽戙傪宍惉偟偰偄傞屄懱偺廤崌偺拞偱娐嫬傊偺揔墳搙偺崅偄屄懱偑師悽戙偵傛傝懡偔惗偒巆傝丆
傑偨岎嵆偍傛傃撍慠曄堎傪婲偙偟側偑傜丆師偺悽戙傪宍惉偟偰偄偔夁掱傪柾曧偟偨嵟揔壔朄偱偁傞丏

The frame of the genetic algorithm was proposed by Holland as a kind of the adjustment system 
in 1975. The mechanism is a technological model by whom the evolution process of the living 
thing that puts the base on the theory of Darwin's natural selection is imitated. That is, it 
is an optimization method of the individual's with high adjustment level to the environment 
having imitated the process of forming the next generation while causing to survive a lot and 
to intersect and to mutate by the next generation in sets of individuals that form the 
generation. 

堚揱揑傾儖僑儕僘儉偺摿挜偼丆戞堦偵懡揰扵嶕朄偱偁傞偨傔丆弶婜抣偵斾妑揑埶懚偟偵偔偄丏戞擇偵揔
墳搙傪棙梡偡傞偩偗偱丆懠偺忣曬傪巊傢側偄偺偱棧嶶揑側栤戣偵傕揔梡壜擻偱偁傞丏戞嶰偵妋棪扵嶕朄
偱偁傞偨傔嬊強揑嵟揔夝偵偲偳傑傜偢丆戝堟揑嵟揔夝偵摓払偟摼傞壜擻惈偑崅偄~\cite{ga_b3}丏偙偺偨
傔丆寁嶼検偺懡偄慻崌偣栤戣丆旕慄宍栤戣摍~\cite{ga_p3}傪夝偔偨傔偵梡偄傜傟偰偄傞丏

The feature of the genetic algorithm doesn't comparatively depend easily on an initial value 
the first because it is a multipoint search method. Because only the adjustment level is used 
secondarily, and other information is not used, it is possible to apply also to a discrete 
problem. It is ~ \cite{ga_b3} that the possibility to be able to reach not only a local, best 
solution but also the global optimum because it is a probability search method is high in 
third . Therefore, it is used to solve ~ \cite{ga_p3} like a combination problem and a 
nonlinear problem, etc. with a lot of computational complexities. 

埲忋偺傛偆偵丆堚揱揑傾儖僑儕僘儉偼嵟揔壔栤戣偵懳偟偰桳岠側庤朄偱偁傞丏偟偐偟側偑傜丆屄乆偺栤
戣偵墳偠偰僐乕僨傿儞僌傗僷儔儊乕僞乕偺愝掕傪偡傞昁梫偑偁傞偨傔丆尰嵼偱偼帋峴嶖岆揑偁傞偄偼丆
宱尡偵婎偯偄偰愝掕偟偰傗傜側偗傜偽側傜側偄丏

As mentioned above, the genetic algorithm is an effective technique to the optimization 
problem. However, it sets based on the trial and error or the experience to have to set 
coding and the parameter according to an individual problem now and. 

摿偵丆懳徾偲側傞栤戣傪偄偐偵昞尰偡傞偐丆偮傑傝偳偺傛偆偵僐乕僨傿儞僌偡傞偐偲尵偆揰偑廳梫偱偁
傞偲峫偊傜傟偰偄傞丏

Especially, how express the problem of becoming an object is thought that it is blocked and 
the point to say whether to code it very is important. 

傑偨堚揱巕偼丆捠忢0,1偺價僢僩僷僞乕儞偱昞尰偝傟傞応崌偑懡偄丏偟偐偟側偑傜杮尋媶偺栤戣偵懳偟
偰偼丆帒尮偺攝暘壜擻検偑偁傜偐偠傔寛掕偟偰偄傞偨傔丆0,1偺價僢僩僷僞乕儞偱偼丆抳巰堚揱巕(幚
峴壜擻偱側偄夝傪昞偡堚揱巕)偺惗偠傞壜擻惈偑崅偔側傞偨傔旕岠棪偱偁傞丏

Moreover, the gene is often expressed by the bit pattern of 0 and usual 1. This..research..
problem..resource..distribution..amount..beforehand..decide..bit..pattern..lethal gene..
executable..solution..show..gene..cause..possibility..rise..inefficiency.


偦偙偱杮尋媶偱偼丆埲壓偺傛偆側僐乕僨傿儞僌傪揔梡偡傞丏
Then, the following coding is applied in this research. 

 (1)丂堚揱巕Gene
     堚揱巕偼丆寛掕曄悢偺揧帤$i$傪昞偡丏偮傑傝丆攝暘梫場傪昞偟偰偄傞丏傑偨丆懳棫堚揱巕偼丆$1\sim n$ 偺惍悢抣傪偲傞丏
     The gene shows subscript $i$ of the decision variable. In a word, the distribution factor is shown. Moreover, 
     the allelic gene takes the integral value of $1\sim n$. 
 (2)丂愼怓懱Chromosome
     愼怓懱偼丆堚揱巕偵傛傝峔惉偝傟偰偄傞丏傑偨愼怓懱挿偼丆攝暘壜擻検Q傪昞偟偰偄傞丏
     The chromosome is composed by the gene. Moreover, the length of the chromosome 
     shows amount Q that can be distributed. 
 (3)丂屄懱
     屄懱偼丆愼怓懱偵傛傝摿挜偯偗傜傟傞屄偱偁傝丆攝暘梫場偺慻崌偣傪昞偡丏偮傑傝丆夝岓曗傪昞偟偰偄傞丏
     The individual is piece characterized by the chromosome, and the combination of the 
     distribution factor is shown. In a word, the solution candidate is shown.
(4)丂廤抍
     廤抍偼丆屄懱偺廤傑傝偱偁傝丆攝暘梫場偺慻崌偣偺廤崌傪昞偡丏偮傑傝丆夝岓曗偺廤崌傪昞偟偰偄傞丏
     The group is a group of the individual, and the set of the combination of the distribution 
     factor is shown. In a word, solution candidate's set is shown. 

(5)丂揔墳搙娭悢Adjustment level function
    揔墳搙娭悢偼丆娐嫬偲偺揔墳搙偱偁傝丆婣懏搙$\lambda$傪昞偡丏乵掕幃3乶偱偼擇栚揑寁夋栤戣偱偁傞偨傔
    揔墳搙娭悢偺愝寁偑崲擄偱偁傞偑丆乵掕幃4乶偱偼婣懏搙$\lambda$偺堦栚揑寁夋栤戣偱偁傞偨傔丆揔墳搙娭
    悢偺愝寁偑梕堈偵側偭偰偄傞丏
The adjustment level function is an adjustment level with the environment, and belonging level $lambda
 is shown. Because it is glancing plan problem of belonging level lambda, in fixed expression 4, the 
design of the adjustment level function is easy though the design of the adjustment level function is 
difficult in fixed expression 3 because it is two purpose plan problem. 

愼怓懱峔憿偺堦椺傪恾偵丆栤戣嬻娫偲堚揱揑傾儖僑儕僘儉嬻娫偲偺懳墳娭學傪昞偵帵偡丏
One example of the chromosome structure is shown and the relation between the 
problem space and the genetic algorithm space is shown in the table in figure. 

%恾丂愼怓懱峔憿Chromosome structure
      堚揱巕嵗 & 1 & 2 & 3 & 4 & 5 Gene loci
      堚揱巕   & 1 & 4 & 9 & 9 & 15  
 
愼怓懱峔憿偺堦椺

忋偺椺偱偼丆攝暘壜擻検Q偼5偱偁傝丆梫場1, 4偍傛傃15偵1丆9偵2攝暘偡傞偙偲傪堄枴偟偰偄傞丏
In the example above, amount Q that can be distributed is 5, and it means two 
distributions 1 and 9 factor 1 and 4 and 15. 丂

昞丂栤戣嬻娫偲堚揱揑傾儖僑儕僘儉嬻娫偲偺懳墳娭學
	栤戣嬻娫(Problem space) & 堚揱揑傾儖僑儕僘儉嬻娫 (Genetic algorithm space)
	攝暘梫場(Distribution factor) & 堚揱巕(gene) 
	攝暘壜擻検(Amount that can be distributed) & 愼怓懱挿 (Length of chromosome)
	攝暘梫場偺慻崌偣 & 屄懱
	攝暘梫場偺慻崌偣偺廤崌(Set of combination of distribution factor) & 廤抍 
	婣懏搙(Belonging level) & 揔墳搙娭悢(Adjustment level function) 


埲忋傛傝丆杮尋媶偱偼抳巰堚揱巕傪慡偔惗惉偟側偄僐乕僨傿儞僌傪幚尰偟偰偄傞丏偝傜偵丆愼怓懱挿偑
捈愙攝暘壜擻検偵懳墳偟偰偄傞偨傔丆攝暘壜擻検偑壜曄偵側偭偨応崌傪峫椂偡傞偙偲偑梕堈偵側偭偰偄傞丏
Therefore, coding that doesn't generate the lethal gene in this research at all has been 
achieved. In addition, it is easy to consider the case where the amount that can be distributed 
becomes changeable because it corresponds to the amount to be able to distribute the length of 
the chromosome directly. 

師偵丆杮尋媶偱梡偄偨堚揱揑傾儖僑儕僘儉偺幚憰僆儁儗乕僞乕傪帵偡丏
Next, the mounting operator of the genetic algorithm used by this research is 
shown. 

 (1)丂慖戰

慖戰偼丆揔墳搙偵墳偠偰娐嫬偵揔偟偨屄懱傪妋棪揑偵慖傇憖嶌偱偁傞丏杮尋媶偱偼丆愼怓懱挿偺堎側傞屄懱孮偛偲偵廤抍傪暘妱偟丆
僄儕乕僩愴棯傪峴偭偰偄傞丏偮傑傝丆揔墳搙偺壓埵偵懏偡傞屄懱偵娭偟偰偼搼懣棪偵廬偄巰柵偝偣丆揔墳搙偺忋埵偵懏偡傞屄懱偵
娭偟偰偼丆搼懣棪偵廬偄憹怋偝偣傞丏
The selection is an operation that chooses the individual that is appropriate for the environment stochastically 
according to the adjustment level. In this research, each individual group with different length of the chromosome 
divides the group, and the elite strategy is done. In a word, it kills out according to the selection rate for the 
individual that belongs to the subordinate position of the adjustment level, and it proliferates according to the 
selection rate for the individual that belongs to the high rank of the adjustment level. 

 (2)丂岎嵆Intersection

岎嵆偼丆妋棪揑偵2偮偺恊偺愼怓懱傪慻傒懼偊偰丆巕偺愼怓懱傪嶌傞憖嶌偱偁傞丏杮尋媶偱偼丆1揰岎嵆傪揔梡偟偰偄傞丏傑偨丆
岎嵆埵抲偺寛掕偵娭偟偰偼丆恊偺愼怓懱挿偺抁偄曽傪婎弨偲偟丆堦條棎悢偱寛掕偟偰偄傞丏偙偺偲偒丆恊偲巕偵偍偄偰愼怓懱
挿偺儁傾偼曄壔偟側偄丏偙偺傛偆側曽朄偵傛傝丆抳巰堚揱巕傪慡偔惗惉偟側偄岎嵆傪幚尰偟偰偄傞丏
Intersection is an operation that rearranges two parents' chromosomes stochastically, and makes child's chromosome. 
In this research, one point intersection is applied. Moreover, it decides it by the uniform random number for the 
decision of the intersection position based on one with short length of parents of the chromosome. At this time, 
the pair of the length of the chromosome doesn't change in parents and the child. Intersection that doesn't 
generate the lethal gene at all has been achieved by such a method. 

 (3)丂撍慠曄堎Mutation

撍慠曄堎偼丆愼怓懱忋偺偁傞堚揱巕嵗偺抣傪妋棪揑偵懠偺懳棫堚揱巕偵抲偒姺偊傞憖嶌偱偁傞丏杮尋媶偱偼丆奺屄懱偺奺堚揱巕嵗偵懳偟偰
撍慠曄堎棪偵廬偄丆懠偺懳棫堚揱巕偵抲偒姺偊偰偄傞丏偙偺偲偒丆嵟椙偺屄懱偼撍慠曄堎偺懳徾偲偟側偄丏
The mutation is an operation that replaces the value of the gene loci on the chromosome that is with other allelic genes 
stochastically. In this research, each gene loci of each body is replaced with other allelic genes according to the mutation 
rate. At this time, the best individual is not targeted in the mutation. 

埲壓偵丆杮尋媶偱梡偄偨扨弮堚揱揑傾儖僑儕僘儉偵夵椙傪壛偊偨傾儖僑儕僘儉傪帵偡丏
The algorithm that adds the improvement to the simple genetic algorithm used by 
this research is shown as follows. 

 乵戞堦抜奒乶丂廤抍敪惗張棟Group transaction
               愼怓懱挿偺堎側傞屄懱傪丆廤抍僒僀僘傪摍暘妱偟偨悢偩偗丆堦條棎悢偵傛偭偰惗惉偝偣傞丏傑偨丆悽戙悢傪0偵偡傞丏
 乵戞擇抜奒乶丂屄懱偺昡壙張棟Evaluation processing of individual
              奺屄懱偺堚揱巕忣曬偵婎偯偄偰丆乵掕幃4乶傪峔惉偡傞丏偙偺偲偒丆夝僨乕僞丒儀乕僗傪僠僃僢僋偟偰婛偵夝偄偨傕偺偼丆夝
              僨乕僞丒儀乕僗偐傜揔墳搙抣偱偁傞栚揑娭悢偺抣傪梌偊傞丏傑偨丆怴偟偄慻崌偣偵偮偄偰偼丆乵掕幃4乶傪夝偔丏
 乵戞嶰抜奒乶丂堚揱揑憖嶌Inherited operation
               慜弎偟偨慖戰丆岎嵆偍傛傃撍慠曄堎曽朄傪梡偄偰峴偆丏
 乵戞巐抜奒乶丂孮昡壙張棟Crowd evaluation processing

悽戙悢偑嵟戝悽戙悢偵側偭偨応崌偵偼廔椆偡傞丏偦偆偱側偄応崌偵偼丆悽戙悢偵1傪壛嶼偟戞擇抜奒偐傜孞傝曉偡丏丂
When the number of generations becomes the number of maximum generations, it ends. One is added to the number of generations 
when it is not so and it repeats from the second stage. 

埲忋偺傛偆側傾儖僑儕僘儉傪梡偄傞偙偲偵傛傝丆愼怓懱挿偺堎側傞屄懱孮傪摨帪偵堚揱揑傾儖僑儕僘儉偵偐偗傞偙偲偑偱偒傞偨傔丆堚揱揑
傾儖僑儕僘儉偺摿挜偱偁傞暲楍張棟傪妶偐偡偙偲偑壜擻偱偁傞丏
Because the individual group with different length of the chromosome can be put on the genetic algorithm at the same time by 
using the above-mentioned algorithm, the parallel processing that is the feature of the genetic algorithm can be made the best
 use of.