AG ORlT P KAG~
By
TINGZHU
Bachelor of Science
Beijing Polytechnic University
Beij ing, himi
1999
Submitted to the Faculty ofthe
Graduate College ofthe
Oklahoma State University
in partial fulfillment of
the requirements for
the Degree of
MASTER OF CIE CE
December, 2003
A GE RAL GENET] ALGORITHM P KAG
Thesis Approved
II
The genetic algorithm i a w L1-known m thod to deal with ptimiz tion in an approximate sense. Ther are many c isting geneti alg rithm oft\; arc package this area. Howev r, no tudie ha b en don ill d aling ith tlu'e differ r presentations allowed in one chromo orne: bit string integer and floating point.
The objective ofthis thesis is to design and implement a general genetic package. The whole package is composed of GAPACK, which is a core package a universal library, and GATST, which is the main control program. This package can process the bit string representation the integer repre ntation, the representation, and any combination of th se three repre entations.optimization problems are tested,including the standard Ro enbrock function, Rosenbrock function, the ballow-ground Rosenbrock function, the xTX the 0/1 knapsack problem and the TSP problem..
111
I \I ould Ii.k to e pr my inc re appre iati. n t m maj r pr fe P. Chandler for hi guidanc, a i tanc and kindn In mpl ting my th wanl to e tend my sin er appreciation to Dr. org . H dri k and Dr. ohpill for their advice and illingness to rYe on my graduat ommitt c.
I also would l1ke to ext nd special appr iation t my parents, ho believed in my abilities, for their moral and financial upp rt and nc uragem Without their support and encouragement I would not ha b n fUlished the study.
Flnally I ant to thank all my fri nd and fi r lh 1r suggestions.
IV
TABLE OF CONTE TS
Chapter I Introduction , 1.1 Principle of genetic algorithms II Literature review : 2.1 Development in the genetic algorithm research 2.2 Existing GA packages , 2.2.1 GALIB 2.2.2 GENESIS , 2.2.3 FORTRAN genetic algorithm driver , , 2.2.4 Other GA packages 2.3 GA general package III Design of a gereral GA package , , , 3.1 Representations , 3.1.1 Bit string representation 3.1.2 Integer representation 3.1.3 Floating-point representation 3.1.4 Mixed representation , 3.2 Data structure and algoritlun 3.2.1 Basic program structure 3.2.2 Program configuration 3.2.3 Basic data structure 3.2.4 A detail example 3.2.5 Running the package 3.2.6 Two special testing problems : rv Test problems , , ,., 4.1 Rosenbrock fLLnction , 4.2 xTx problem , 4.3 011 kanpsack problem , 4.4 TSP problem V Results , 5. I Rosenbrock function , 5.2 xTx problem , 5.3 0/1 knapsack problem , v
5.4 TSP probl m VI Future work.········· References Appendixes Appendix A General package GAPAK Appendix B Test package GATST Vl
LIST OF TABLES
Table Table 1-1 Initial population in One Max example Table 5-1 The result of standard Rosenbrock function with two floating-
Table 5-2 The result of standard Rosenbrock function with one integer
Table 5-3 The result of flat-ground Rosenbrock function with one integer
Table 5-4 The result of holloW"-ground Rosenbrock function with one
Table 5-6 The result of xTx problem 3 integers and 2 floating-points input Table 1-2 Population after single-point crossover in One Max example ..: Table 1-3 Population after mutation in One Max example Table 3-1 Binary and Gray codes Table 3-2 Weight and value infonnation of a knapsack problem points input. input and one floating-point input.. input and one floating-point input.. integer input and one floating-point input Table 5-5 The result of xTx problem 5 floating-points illpUt.. Table 5-7 The testing data of a 011 knap ack problem Table 5-8 The result of a Oil knapsack problem Table 5-9 The testing data of a TSP problem Table 5-10 The result of a TSP problem VII
Figure
Figure 1-1
Figure 2-1
Figure 3-1
Figure 3-2
Figure 3-3
LI T OF FIGURE
The procedure of the basic binary genetic algori.thm The structure ofGENESIS : The binary-to-gray and gray-to-binary procedures The flow chart of a general GA package Source code ofthe fitness function of the knapsack problem V III
Figure
Figure I-I
Figure 2-1
Figure 3-1
Figure 3-2
Figure 3-3
LIST OF FIGURE
The proced ure of the basl. c bm' ary geneti. c a1 gon.t h m The structure of GENESIS " The binary-to-gray and gray-to-binary procedur s The flow chart ofa general GA package : Source code ofthe fitness function of the knapsack problem ViU
eH PTER.l
[ TROD eTION
Optimization is one of the mo t important cat gories of computational problems engineering and mathematiCal studies [1]. or instance the Traveling Salesman (TSP) [2] is an optim.ization problem. If a salesman, starting from his home visit exactly once each city on a given list and then return home, the optimization
problem is to find the order in which he visits all cities so that the total distance is as small as possible. To implement the TSP problem, there is a graph to represent traveling situation, in which the nodes (cities) of a graph are connected by directed (routes), where the weight of an edge is the distance between two cities [3]. Solving problem exactly requires exponential time, as far as is known. For example, problem deals with 4 cities, it's practical to use exhaustive search. That distance of every possible route will be calculated by hand. in uch an approach are only 3! different routes. Only 6 distances need to be computed, and it is easy the minimum among 6 choices. If the nwnber of cities increases to 10, the distance needs to be picked out of 362880 choices. very city added to the T will make the problem more difficult and mu~h more time consuming. The algorithm is one of the successful ways to solve optimization problems.
1.1 Biological background
Before introducing the genetic algorithm, some biological terms, used in algorithm, should be clarified. All living organisms consist of cells. in every 1
the same s t of chromosol1l hr mo om are string of D A chromosom
consists of gene. Each g n ncode a particular protein. Ba i ally, it can each gene encodes a trait fOr ample, tl1 olor of hair. Po~si I etting of black or blonde are called all I s. Each gene has it 0 n position in the chromo which is called a locUS.
The complete set of genetic material (all chromosomes) is called the genome. particular set of genes in genome is called a genotype. The genotype is the coded, inheritable infonnation carried by all living organisms. It is copied at cell division or reproduction and is passed from on generation to th phenotype is the set of the physical and mental characteristics, such as intel1ig 1.2 Principle of genetic algorithms (GAs)
Genetic algorithms wer deY loped based on the idea of Darwinian survival ofth or evolution [4]. A genetic algorithm is a computational model fbiological The basic idea of genetic algorithms was invented by Holland. In Holland's Adaptation in Natural and ArtifiCial 'Ystems, publish d in 1975 [5], he genetic algorithm. that would generate a new population of "chromosomes" generation to the next by using four operators: sel ction, crossover, mutation inversion. Holland introduced some important concepts for genetic algorithms. problem that a genetic algorithm is to solve, a chromo ome is one of the solutions. Every chromosome consists of "genes" (i.e., bit strings), and consists of a string of "alleles" (i.e., 0 or 1). Selection selects the chromosomes 2
fitness which are then cOrnbin d to produce mor off: pring. 1'0 0 er combines single chromoSomes to Create a nev chromosome. Mutation randomly changes value of some locations in tile chromosome, i.e. from I to 0, or 0 to I. Inversion the order of a contiguous section of the chromosome.
The traditional genetic algorithm. usually uses a binary bit-string representation. representation does not always d al ith data contain d in a prabl m solutions directly. Tlus r presentation may ncode original numerical (d cimal) into a bit string of '0' and' I '. The g netic algorithm always deal with optimizing array of possible solutions. The array of possible olutions is called a population which each solution is called an individual. When a g netic algollthm process the array of solutions needs to b initializ d, which means a population of individuals created somehow, perhaps randomly. In the binary repr sentation, every individual bit string and can be thou ht ofa a andidate solution. In rdcr fI r the g nctic to evaluate a pas ible solution, ther must. be a m a ur ment n h w successful is, which is call d the "fitness value" [5]. The fitness value is used t s rt the solutions, c Iupare, and select individual solutions for further g n rati n. population of solutions is compl tely evaluated 'three fundamental operati ns, eros 0 er and Inutation, n ed to be xecuted, one by one.
A basic binary genetic algorithm should work somewhat as follows [6].
3
1. lnitiaLize: G n rat a random population of n chr
solutions for th probl I'D
2. Evaluate: E aluat tb fitn ss f( ) of a h hrolllosome in th
population
3. GA operations: r ate a new population by repeating the following
steps until the new population is complete.
a. Selection: Select two parent chromosomes from a population
according to their fitness (the better fitness the bigger chance be selected).
b. Crossover: With some probability, crossover the par nts one or two new offspring.
c. Mutation: With some probability, mutate new offspring more positions in a chromosome.
d. Accepting: Place new offspring in a new p pulation.
4. Replace: Use the new generated population for a further "gen ration" the algorithm.
5. Test: lfthe end condition is satisfied, stop, and r tum the best solution current population.
6. Loop: Go to step 2.
Figure 1-1 The procedure ofthe basic binary genetic algorithm
For example, there is a simple test problem called One Max in which the maximize the number of occurr nces of the digit 1 in an arbitrarily long bit string 4
Assuming th I ngth of th bit string is 8 th r pr entation of each indi idual string of 8 ones and zeros, i. . 10011000. For the fitn fWlction ther is way to evaluate a bit string which is to count the numb r of ones in a r pr entation. instance, the bit string 10011 0 a has the fitness value 3, h reas 00000000 fitness value O. Suppose the population size is chosen as 4 Per = 0.7 and 0.001. During initialization, four bit strings (chromosomes) are randomly gen is a bit string in the population. After the initialization, the highest fitness in Xz = 6. The average fitness value equals to (2 + 6 + I + 3) /4= 3.
Table 1-1 Initial population in One Max example
Bit string Fitness value
Xl = 00000110 2
Xz = 11101 110 6
X3 = 00100000 1
~ - 00110100 3
Using fitness-based selection, four individuals (two sets of parents) must randomly, with probabilities proportional to their relative fitness values. In the suppose that the two parent pairs are [X2, Xt] and [Xz, X3]. Once a pair of selected, crossover is used between them with probability Peros, producing two If no crossover is used, then the offspring are exact copies of each parent. 5
the example, single-point crosso er takes place betw en parent and (rand.omly chosen) third bit position, fomling the offspring· 2' = 11110 LOO 00101110, while no crosso er is effected between parents X2 and X), fonning offspring that are exact copies of 2 and X).
Table 1-2 Population after single-point crossover in One Max example
Bit String Fitness value
X2 = 11110100 5
X2 = III 01110 6
X ] 3 = 00100000
X~ =00101110 4
Next, each offspring is subject to mutation with probability PmU13lC per bit. For suppose the offspring X2" 1 I 1 10100, is mutated at the sixth position to fonn 11110000, the offspring X 2 is mutated at the first bit position to fonn X2· = and the offspring ~' and X 3 are not mutated at all. The next generation created by the operators of selection, crossover, and mutation is as foHows:
6
II
Table 1-3 population aft r mutation in On Max xarnpl
Bit String Fitn ss alue
X 4 2 = 11110000
X 5 2 =01101110
X I 3 = 00100000
)4 = 00101110 4
In the new population, although the best individual with fitness 6 has been average fitness has increased, (4 + 5+ I + 4) / 4 = 3.5 which is larger than initialization fitness value. Repeating thjs procedure, the genetic algorithm probably eventually find the optimum string, i.e., 11111111 with maximal fitness value 0[The rest of this thesis is organjz d as follows: hapter [] introduces th d v lopm GA research and some GA packages. hapter 1J] discLlsse four GA representations lays out the structure of a general genetic algorithm. hapt r IV is a hort introduce six test problems. Chapt r V contains the results and analysis. concludes this thesis and points out certain possible directions for further research.
7
CHAPTER II
LIT RAT RE REVIEW
Many concepts in genetic algori,thro res arch ar borrow d from natural evoluti original focus of the res arch 'as t use th principle of olution (the Darwinian
principle of "survival of the fltt st") to simulate th adaptive natw'e of natural for u e in artificial systems. Since the first idea of the genetic algorithm was proposed, lot of research has been done in this area. In this chapter, the related research GA software packages will be introduced, respectively.
2.1 Development in the genetic algorithm research
In the 1950s and 1960s, many scientists studied evolutionary sy tern. They contributed
their ideas that the evolution could be used as an optimization tool for ngineering
problems [9] [10).
In the 1960s, a new strategy called "evolution strategy" was introduced by Rechenberg
[11). In his evolution strategy, Rechenberg proposed a model which starts "population" of two individuals, one parent and one offspring. The offspring by mutating one parent. In his paper, the model is used to optimize real parameters for devices.
8
Richard Rosenberg perfonned his computer tudy of 10 d, small populations genetic algorithm area [12]. ff mad a d tail d study on th complicated r lationship
between genotype that is a particular set of gene and phenotype that is th orgaojsm's
physical and mental characteristics. R lations among the number of genes, crossover
probabilities, and the rate ofadaptation were developed.
In the 1960s, Holland invented the idea of genetic algorithms. In .1975, presented genetic algorithms and gave a theoretical framework for adaptation under genetic algorithm in his book Adaptation in Natural and Artificial S stems [schema theorem was provided by Holland. A schema is a naturally defined subset space of fixed-length binary strings. Holland's schema theorem has three parts, selection, one for crossover, and one for mutation. The selection part is exact, while crossover and mutation parts are approximations. Holland's genetic algorithm milestone of the developing history of genetic algorithms. Almo tall CutTent algorithms are based on Holland's GA. Holland used only bit strings chromosomes.
Based on Holland's GA, Goldberg wrote a Pa'scal computer code called the genetic algorithm (SGA) [13]. In SGA, Goldberg used non-overlapping populations, reproduction, crossover, and mutation to optimize a function of variable. This variable was represented as an unsigned binary integer. Goldberg two rules for designing GA COding: the principle of meaningful blocks and the of minimal alphabets. He sUUUnarized previous researchers' work, pointed out 9
advanced operators and t chniques in g netic earch and machin leaming and genetic-inspired mechanisms such as dominance tran location and se ual differentiation.
In ] 999, Mitchell presented an 0 eTview of the de elopment and application algorithms since they were proposed, and discussed some new idea from genetics as diploidy, inversion, gene doubling, and deletion [14]. She explored several methods in the GA literature including binary encoding many-character and real-encoding, and tree encoding. She thought the development of further encoding should be in the direction of adapting encoding and using encodings. Crossover primary operator in GA was discussed. Mitchell emphasized that research for at different stages needs further work.
2.2 Existing GA packages
As the idea of genetic algorithms developed, many different GA software packages created for dealing with GA-related problems. everal GA packages will be r the following sections.
2.2.1 GAlib
GAlib was developed by MIT in 1995, which is a full-featured and extensible algorithm package written in C++ [15]. GAlib can be used under many systems, such as DOS, UNIX, Windows 3.1, Mac as and Linux.
10
GAlib can deal with different valuation function, repr sentations and genetic operators.
The genome class and the genetic algorithm class are the most important class Every genome instance represents a singl solution to the us r-defined problem. genetic algorithm obj ect defines the process of the evolution which uses an evaluation
function (defined by the user) to evaluate every genome and uses GA operators generate the new offspring. GAlib provides many examples of representations operators, so users can use the built-in representations and GA operators with little modification. According to different problems to be solved, evaluation functions different. Users can define their own. evaluation functions. With the representation, operators and the evaluation function, users can use GAlib to implement a GA-problem.
In GAIib, the data structure is called a GAGenome. The library contains fOUI genomes: GAListGenome, GATreeGenome, GAArrayGenome GABinaryStringGenom . The e classes are derived from the base AGenome class. example, if a user is trying to optimize a function with 3 r al param ters, he/she genome as a I-dimensional array of floats with three elements.
GAlib includes four genetic algorithms [16] which differ in the way they create offspring and replace old offspring in every generation.
(1) Simple genetic algorithm [16]
The simple genetic algorithm was described by Goldberg. This algorithm uses pOPUlations and optional elitism, which keeps some number of best-II
chromosomes of last gen ration. Eery gen ration gen rates an entir population of the offspring,
(2) Steady-state genetic algorithm [16]
The steady-state genetic algorithm uses overlapping populations. In this algorithm,
the user can specify how many genomes should be replaced in every generation some steady rate.
(3) Incremental genetic algorithm [16]
In this algorithm every generation consists of only one or two offspring. algorithm, users can use replacement methods to define how the new generation
should be put into the population. For instance, a newly generated offspring replace its parent, replace a random individual in the population, or replace individual that is most like it.
(4) Deme genetic algorithm (16]
This algorithm contains multiple populations in parallel using a st ady-state algorithm.
The algorithm moves some of the offspring from one population to populations.
For the representation, GAhb recommends users to pick an appropriate representation the problem to be solved. Users can choose a purely numeric representation vector of real numb ers. T h1' S couI d be I. mplemented as an array a freia nbum ers, string of bits that map to real numbers.. Since four main data structures, GAListGenome,
12
ayGenom and G BinaryStringG nome are d fin d in GATreeGenome G
carr sponding r presentations are upported.
GAhb has three GA operators --- the initiali ation op rator th mutation op rator crossover operator. The initialization op rator initializes the genome. In generation, the initialization operator is called to initialize a population. The operator defines the procedure of mutation. This operator will check a pr mutation rate and mutate every genome according to different genome types. example a typical mutation for a binary string genome is to fljp the bits in the string a given probability. A typical mutation [or a tree is to swap sub-trees with probability. The crossover operator interchanges parts of two parent genom s to an offspring.
2.2.2 GENESIS
GENESIS is a C version genetic algorithm package d veloped by John J. refi 1994 [17]. It is a system for function optimization ba ed on genetic search techniques.
Like GALIB, GENESIS also requires users to pr~vide their own evaluation The structure ofGE SIS is shown in Figure 2-1.
13
Procedure
begin
t = 0;
initialize P(t);
evaluate structures in P(t);
while termination condition not satisfied do
begin
t=t+ 1;
select P(t) from P(t-l);
recombine structures in P(t)·
evaluate structures in P(t);
end
end
Figure 2-1 The structure of G ~ NBSI
Every structure in population P is a binary string of 1 ngth L. During every g step, the current population is evaluated and GA operations are apl'li d, then population of candidate solutions is fonned.
GENESIS has a specific representation of possible solutions. The struchlre has levels. The highest level, "floating-point" representa~ion, is the appropriate lev 14
many numenc optimization problem . At thi 1 vel the us r can s the stmctures as vectors of real numb rs. Th middl I v "string" r presentation
represents structures as arrays of characters. For example th structure 111010 represented by the string" III 0 10". The lowest I el "pack d" representation, i maximize both the space and the time efficiency. Us rs can t see this lev representation. For every parameter, the user specifies its rang its number of and its output format. The system then automatically converts floating-point.inputs string representation, and translates between the user-level genes and the representation levels.
The initial population P(O) is usually chosen at random. The structures of the population
P(t+ 1) are chosen from the population pet) by the selection method. The default selection
procedure is a stochastic procedure based on an algorithm by James Baker [18]. The is to allocate to every structuTe a portion of a pinning wheel proportional according the structure's relative fitness. A single spin of the wh el determin s the number offspring assigned to every structure. The selection pointers are then randomly and the selected structures are put into the new population. In spite of th selection, there is another option. If the "R" option is selected, selection is based ranking algorithm, in which the probability of selecting a structure is proportional index in the population, Where the index of the best structure is Popsize-1, and the of the worst structure is O. Ranking selection helps to prevent premature convergence.
15
After the s I ction, two G op rations will b e cut d. ros 0 er changes (bits in a bit string) among the select d par nt . G ESI u t11 doubl eros 0 chooses two crossover points and e changes th s tion b tw n th s points. mutation is applied to every structure in th new population. With a mutation rate the probability deciding if a structure is going to be mutated som selected structure
randomly flips bits for mutation.
2.2.3 FORTRAN genetic algorithm driver
David L. Carroll wrote a FORTRAN version of a genetic algorithm driver in 1991 This FORTRAN GA driver initializes a random sampl of indi iduals with different
parameters. The representation is binary string. The selection method tournament selection with a shuffling technique for choosing random pairs for The crossover operation has two choices, single-point crossover and uniform (crossover. Advanced mutation m thods, jump mutation and cr p mutation ar candidate mutation choices. Jump mutation randomly switches a bit from I to 0, oto 1. It goes through every bit in the string and exposes to th possibility of mutation.
Creep mutation randomly switches the values of two adjacent bits in the binary Carroll added some advanced GA technique in his .FORTRAN package, such as that is a process of separation of individuals according to their states in the s arch or maintenance of diversity by appropriate techniques, i.e. fitness sharing, and micro-which i a genetic algorithm with a very small population and a re-initialization process.
The following parameter values are recommended for use in this FORTRAN GA 16
mlcroga = I. (Enables micro-Gen tic Algorithms 0 IS for nonnal cony opration; I. is for micro-GA operation)
npopsiz = 5 (The population size of a GA run)
maxgen = I. 00 (Maximum number of generations to run by the GA)
iunifnn = I. (Enables uniform crossover, 0 is for single-point crossover 1 crossover)
Carrol] provided a tip about how to choose population size.
npopsiz = order[(Vk)(2**k)] for binary coding
where 1 = nchrome and k is the average size of the schema that is asp cific model. (Effectively k equals to the average number of bits per parameter, approximately equals to nchrome/nparam, rounded to the nearest integer. means the number of chromosomes. nparam means the number of parameters).
To use this FORTRAN GA package, arl'oll recommends using techrtiques.
Binary coding (the only option in the ORTRA ~A package)
Tournament selection (the only option in th FORTRAN G package)
U'1iform cros ov r (iunifrm=l)
Creep mutations (icreep=l)
iching or sharing (iniche=l)
17
liti m Ilte=l
2.2.4 Other G pac ag
Thre GA packages w r d saibed in the a 0 paragraph. luall th r ar other GA packag s. G IS a crsiOI1 of g n tic alg rithm pa kag. [t nix and Linux en irorun nts. Thi packag can us_ a GA techniqu to find the to a classification problem with a neural network. Generator written in ME· help to solve many problems. It is designed to interact with Microsoft EX Windows. GAGS is a GA package written in Perl, and it works in Unix and Linux The best place to find existing GA packages is perhaps the FAQ (Frequently Questions) file for the comp.ai.genetic newsgroup on Usenet: cb ck faq-doc-2.2.3 GA general package
After reviewing several genetic algorithm packag~s. 1t is obvious that no general package has been mentioned. Most existing GA packages use some specific way to deal with all input parameters, such as the binary string representation the most popular encoding. In a real optimization problem, the representation parameters can be in different formats. Some problems might only deal with values, some problems might handle integer value, and some probl ms 18
solve combiJlation input stylI.. an input might ha three parts --- bit strings. integ and floating-point numbers. E isting package do not handl a ide ariety types, especially with combination style inputs. gen ral pa ka e i ne handle the variety of problems GA packag s can't handl g n ral G package provided in the next chapter.
19
CHAPTER III
D.ESIGN OF GE RAL GA P K G i
3.1 Representations
There are lots of representations for optimization problems. orne of those represented in four categories --- the bit string representation the integ r repr the floating-point representation and the mix d representation that might combination of the bit string representation, the integer repr sentation and the representation. For the first three representations, tbey have their own methods, GA operations and even specific GA techniques. For the mixed representation
depending on the combination mode, it can have different mixed encoding ways operations. All four repres ntation will be gon through in th following ection.
3.1.1 Bit string representation
As introduced in chapter I, the bit string repr sentation is a traditional ncoding widely used in genetic algorithms. The mutation is just randomly nipping bits, is selected to mutate, then after mutation, the returned bit will be "0", and vice The crossover can have many choices, such as the single point crossover, the point crossover, the random crossover and the arithmetic crossover. In my general package, the single point crossover, the double point orossover and the random 20
are pro ided a options for the bit string r presentation. Th folio ing is the definition those three crossover operations.
I) ingl point r er
I ct one point to di id til hr Jl1 mint two left part and right part. Once a ingl point i par nts, th 1 one off: pring is copied from one parent, th right part that orr: pring i opi. the s cond parent. The I ft and ri ght part 0 f th th r ffspring ill remaining parts from the two parents.
Example:
uppose two parents 10000III and 1111 110 ar I cted for a singl cro SOy r and position 4 i chosen for tJ1 plitting point. The proc s is a 100001I 1+ 1111 1I 00 = 100011 00
10000111 + 11111100 = Ull 0111
(2) Double point crosso r
The doubl point eros over divides the chr mo me inl three parts: left, middl right. Once two point ar sleeted [or tw par nts, the left part of ne copi d from one parent the middl part i copied fr m the se ond parent, light part i copied from th first par nt. Til three parts f the oth r offspring copi d from th remaining parts of two parents.
21
ampl
T par nt 1 111 I 1 and 101 11 ar sit d 1i r ad ubi p inl. cr po iti n 2 and 5 r splitting pint. h pr e i a fl 01011111 + 10100011 =01100lLl
01011111 + 10100011 = 10011011
(3) Random crossov r
In the random crossover each bit or gene is selected randomly eith r from parent or from the second one.
Example:
Two par Ilt 0111 101 and 10011101 arc elect d fi r a rand m r ss random position I, 4 and 6 are cho n fi r th splitling pint. h pr cess follows:
01110101 + 1001 HOI = 0001 ] 101
01110101 + 10011101 = I11JOI01
3.1.2 Int geT repres ntation
The integer representation is one of the main encoding methods in GA implementations
because some optimization functions deal with pure integers, or some problems have a mixed representation which contains one or, more integers. For the 22
required in math probl m the cr S 0 er and th mutation op ration ar sam floating-point which ill be co r d in th n t floating-point repr s ntation One thing making integer rep res ntation diffi r nt from oth r tv 0 r pr s ntation Gray coding [21]. The objective of Gray coding is to move the genetic algorithm to the problem space. When Gray coding is used for th integ r representation should be converted to a bit string first. Gray coding is showed in Figure 3-1.
Procedure bimuy-to-Gray
begin
gl =bl
for k = 2 to m do
gk = bk- I XOR bk
end
Procedure Gray-to-binary
begin
value = gl
bl = value
for k = 2 to m do
begin
if gk = 1 then value = NOTvalue
bk = value
end
Figure 3-1 The binary-Lo-Gray and Gray-Lo-binary procedures
23
The Gray coding repr nlation ha the prop rty that an two point ne t to each the problem space diffl r by on bit only. Table 3-1 i an e ample of the binary the corresponding Gray code.
Table 3-1 Binary and Gray codes
Decimal Binary Gray
a 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 aIII
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 11 1I
11 1011 1110
12 1100 1010
13 liOI 10 II
14 1110 1001
15 1II 1 1000
The advantage of Gray coding is to mak crossover pr erv locality. For instance decimal numbers 7 and 8 are chosen to crossover. The corre ponding representations of 7 and 8 are a111 and 1000. Suppose a single point crossov r and then position 1 is chosen for the splitting point. After crossover, two offspring be 0000 and 1111, which are a and 15 respectively in their decimal repre entation. obvious that the offspring after crossover operation are not satisfactory b cause somewhat far from the original mating parents 7 and 8. The offspring close to parents 24
expected. With Gray coding two binary repr ntations 011 Land 1000 are transfonned
to Gray codes fust. 0100 and 1LOO ar corre ponding Gray od s for alII and the same single point crosSO er is applied to the tran form d Gray codes a 100 will be the offspring after crosso er operation. 4 and 12 ar th corr sponding representations for 01 00 and 1100, which are closer to the par ot 7and 8 offspring 0 and 15 from the example without using Gray coding.
3.1.3 Floating-point representation
Genetic algorithms are used to solve mathematical optimization problems. As known, the parameter values of a math problem are often floating-point values given domain. To handle such problems, the genetic algorithm needs to treat floating-point values without any conversion. Different crossover and operations are needed for the floating-point encoding [22].
(1) Crossover for floating-point r presentation
Suppose parenti (P II , P12, PI), P14, P15 , ... , Pin) and parent2 (P I P22, P23, P24, P2n), in which P11 , PI2 etc. and P21, P22 tc. are floating-point values are chos crossover. It seems that the simplest method i to choo e one or more points chromosome as crossover points. Then the param t rs betw en thes point ar between the two parents, which is just like what the bit string representation does. example, position 3 and 5 are selected as splitting points, the two offspring offspringl (PI (, P12 P13, I P24 , P25 I, ... , Pin) and offspring2 (P21 , P22, P23, I P14, P2n). The problem with this double point crossover method is that no new infonnation 25
produced in the off: pring. r floating-point alu that was randomly initiat pass d to th next generation ith the sam alue. only in diffl r nt combinations.
Although this crossover method ork fine for th bit string r pr ntation it work well for a floating-point repr sentation becaus it only int rchanges some chromosome, not changing any "gene value which can lead to premature.
Haupt and Haupt provide another crossover method suitable for floating-point vaJues This crossover randomly selects a parameter in the first pair of par nts to be the cro point.
a = roundup {random * par} Npar: number of parameters.
Parent] = [P II P12 Pia .. · PI par]
Parent2 = [P21 P22 P2a ... P2 par]
Then the selected parameters are combined to [onn new parameters that will appear the offspring:
Pnewl =P1a - P[P la - P2a]
Pnew2 = P2a + P[P la - P2a]
where P is a random value betw en 0 and 1. The last step is to complet th with the rest of chromosome:
Offspringl = [PI I PI2 .. , Pnewl ... P2 par]
Offspring2 = [P21 P22 ... Pnew2 .. , PINpar]
For example, suppose chromosomeI and chromosome2 are selected to do a crossover.
chrornosomel = [3.2879, 1.9638]
chromosome2 = [6.459].8.6674]
26
A random number generator select PI a tb pia e of th cro r taking place random number p is selected as 0.7146. Th n w off: pring ar
Offspring] = [3.2879 - 0.7146 * 3.2879 + 0.7146 * 6.4591. 8. 674]
= [5.5540, 8.6674]
Offspring2 = [6.4591 + 0.7146 * 3.2879 - 0.7146 * 6.4591 1.9638]
= [4.1930, 1.9638]
This crossover method will be used in my general GA package. The input mode shown in the input file. The bit string mode is controlled by two variables nBitst lenStr, which represent how many bit string variables and their lengths in a chromosome.
The integer mode is controlled by the variable nlntgr, which represent how many variables in a chromosome. The floating-point mode is controlled by the variable which represent how many floating-point variables in a chromosome. nBitst, nlntgr nFloat have no relationship with GA operations.
For example, nBitst=O, n1ntgr=0, nFloat= I, which means th re ar only one variable for the input. Suppose nchrom, the population ize, is et to 10. generation 10 chromosomes will be applied for G'A operations. Two chrornosom floating-point values in this example, will be picked to crossover with Haupt and crossover method. If nBitst=O, nIntgr=O, nFloat=3, nchrom=10, there are thr e variables, and each variable is independent to do GA operations chromosomes in every generation. In every generation, two floating-point values floating-point variable will be picked to do GA operation. 0 matter how many 27
111 the input file, different vadabl n ve interact with cach other.
nlntgr=J, nFloat=J, nc 'om=lO, ther ar on it string valiahle with 4-bit-long, integer ariable and one floating-point variable. Dim r nt ariabl s do not interfere others' GA op rations. The bit string variable will apply th A operation for bit The integer variable will apply the G operation for integers. The floating-variable will apply the GA operations for floating-point values.
(2) Mutation for floating-point representation
The tTaditional mutation method works weB for the binary genetic algorithm. floating-point representatioD, traditional mutation i not suitabl any more. In Haupfs
book, a modified mutation method is provided. If [PI P2 ... Pk ..• PNPll.] is a chromo and Pk is selected for the mutation, in mutation Pk will be deleted and replaced with random number chosen from the domain that is in the current pool of chromosomes,
which may in a much smaller interval than the chromosom s in the original lornain.
Using the original domain could prevent GA convergence. The new off: pring generated as [P r P2 .•. Pk ' ..• PNpllr], For example, the original parameter domain is There are 6 chromosomes in the current pool, and chromosome, = [4.9678, 3.2296], (4.9678) is selected to mutate. In the other 5 chromo omes, the values of the element are 4.0037,3.8629,4.3590,5.1882 and 4.6158 respectively. [n the mutation, original value of PI, 4.9678, is deleted; a random value between the domain [5.1882J will be selected. After the mutation, the possible value of chromosome, [4.5673, 3.2296].
28
3.1.4 Mixed r pr s ntation
A mixed repres ntation [24] doe not ha its 0 1 G In thi g n package, it i easy to form a combination mode because the packag will apply GA operators to corresponding representations with the infOlmation from th input The detailed structure will be analyzed in the next ction.
3.2 Data structure and algorithm
The whole package is written In A.N.S.1. Standard FORTRAN 77 a ub FORTRAN 90. The main algorithm used in tbis package is the simpl gen tic algorithm
of Goldberg which uses non-overlapping populations and the elitism te hnique. generation generates an entirely new population of offspring and the nElite chromosomes from the last generation are kept.
3.2.1 Basic program structure
The package is composed of two parts, GAT T and GAPAK.
GATST is the test program, including
InputO is to load the configuration variable and some problem specific input (such as the TSP problem's CITY information etc.)
EvalO is to call the user-defined FuncO and calculate the fitness value.
FuncO is the user-specific evaluation function.
29
GAPAK is the core and general G packag including
Main
lnitO is to randomly generate a gene (part of the chromosom ) b tw n a data range or close to a predefined starting point.
SelectO is to provide a GA selection operation bas d on the fitn ss distribution.
EvalcnO is to evaluate the fitness of each chromosome.
CroverO is to provide a GA crossover operation to generate n w chromosom MutateO is to provide a GA mutation operation to generate new chrornosom ElitO is to retain the best-fit oolite chromosomes from the last generation.
DumpO is to print out a chromosome's detailed information.
ShbestO is to print out the final result.
GrayO is to do gray code transforming on integer.
DegrayO is to do degray cod transforming on integ r.
i2bO is to convert integ r to bit-string.
b2iO is to convert bit-string to integer.
CsortO is a subroutine of comb ort.
30
----------------------------------------------
Figure 3-2 is the program flo\! chart:
GATST GAPA K
[nput
Wt
Eva!
Select*
rover*
Mutat *
Evalcn*-call Eval & Elit
Shbest*
*m ans loop for multiple generation
Figure 3-2 Th Dow chart of a gen ral GA packag
GAPAK is a general package which contains main and all general GA operations. users use this whole package, nothing in GAPAK will be changed. sers can GATST package to run their own problems, because all probl m-d pendent code GATST.
31
3.2.2 Program configuration
Configuration file ga.inp defines program p cific s tting . H r ar th d [mitions:
Variable input modes
This general GA package can deal with four diffi r Ilt input modes --- bit integers, floating-points, and their combinations.
The bit string mode is controlled by two variables: nBitst and lenStr.
The integer mode is controlled by the variable nlntgr.
The floating-point mode is controlled by the variable nFloat.
The gray coding option
The variable nGray defines the integer GraylDegray coding option.
The initialization range
The variable uLimit defines the upper limit of chromosome values.
The variable dLimit defmes the lower llmit of chromosome values.
The initialization starting point
The variable nStart defines the initial starting value for each variable.
The program control(input ()in GATST)
The variable nchrom defines the population size.
The variable mrate defines the mutation rate.
The variable crate defmes the crossover rate.
The variable maxgen defines testing generations.
The variable ctype defines the crossover type for bit string encoding.
The variable nDbg defines the debug output flag.
32
Th ariable nElit defin s ho\! many most fit chromo om \! ill b k pl from generation.
The external variable control
The variable nvar defines external ariabJe counts. n ar u d for TSPlKnapsack problem. For example if th re is a 10-city TSP problem nvar=there is 5-sack Knapsack problem nvar=5.
The variable nUniq is a flag to justify if the chromosome r quir unique expres nUniq is used for the TSP problem. [t notifies GAPAK that the chromosome be unique. For example, in a 5-city TSP problem, the chromosome 12245 i acceptable.
3.2.3 Basic data structure
GAPAK uses a very general and r asonablyeffici nt way to st r th p pulations.
Bit strings
Bit strings are stored in a three-dimensional array bit ts(I,J,K) in which I stand the chromosome index, J stands for the bit string index, K stands for th bit index.
Integers
Integers are stored In a two-dimensional array ints(I J), in which I stands for chromosome index, J stands for the integer index.
Floating-point values
Floating-point values are stored 111 a two-dimensional array floats(I,J), in which stands for the chromosome index, J stands for the floating-point gene index.
33
The fitness
Fitness values are stored in a one-dim nsional array fit I) In hi h 1 stands chromosome index.
The GraylDegray encoding
The conversions between binary codes and Gray codes are tared in array bits(I), which is temporarily used to store the converted bit for the integer representation.
The starting point array
The starting point array is a one-dimensional array st(l) that stores the starting defu1ed in the configuration file. The starting point array only applies to floatingpoint
chromosomes and integer chromosomes. It does not work with bit strings. strings will ignore starting point array. For example, if you set (-1.2 1.0) start.ing poi.nt, the first population will start from (-1.2 1.0).
The external variables
External variables are stored in a one dimensional array xvar(I) and yvar(I). TSP problem and knapsack problem need additional input infomlation. The problem needs the city locations; the knapsack problem needs weight/information. For a TSP problem, the x-coordinate value will be saved in xvar(y-coordinate value will be saved in yvar(I). For a knapsack problem, information will be saved in xvar(I), value information will saved in yvar(I).
34
The combination mode
There is no specific code for the mix d encoding mod . GAP r ut th control bit string, the integer and th floating-point algorithms ba d on th d finition configuration file. Any number of combinations just work in th same ay as a encoding. The input mode should follow the following order: the bit string part integer part, and then the floating-point part.
The GraylDegray option
Integers can be represented either in binary or in Gray codes. Gray codes should better. Only the integer representation can use GrayfDegray to improve GA p rforrnance.
GAPAK calls GrayO at InitO or SelectO, and the GATST calls DegrayO before the non-GA operation EvalO.
The elit operation
Strictly speaking, eli to is not a GA operation. It just t r s th n lit 1110st chromosomes in the last positi ons of bitStsO, intsO, floatsO and fitO arrays. accumulated best values are retained gen ration after generation, and are print the final shbestO subroutine.
3.2.4 A detailed example
The following is a close look at how the combination mode work .
Let's take a sample of the Rosenbrock function with two parameters: xl is an integer, is a floating-point. It e aluates the minimizing function of
35
F(x1 x2)=10 *( 2_XI22+( 1-1 2 inth domain-3<=xl 2<=
The starting point is (-1.2 1.0).
Step 1: Prepare the ga.inp input file
nchrom 10 (10 chromosome per population)
mrate 0.1 (mutate rate 10%)
crate 0.3 (crossover rate 30%)
maxgen 1000 (running for 1000 generations)
nDbg (minimum debug info)
uLimit 3 (range lower Jjmit)
dLimit -3 (range upper limit)
ctype 0 (not used)
nBitSt 0 (no bit string encoding)
lenStr 0 (not used)
nlntgr 1 (variable xl)
nGray 0 (not used)
nFloat (variable x2)
nStart 2 (2 start point x1=-1.2 x2=1.0)
nUniq 0 (not used)
nElite 2 (2 most fit chromosomes are kept)
36
Step 2: Rlmning GAT T t t program
(1) Call lnputO
Load variables in the input file and the starting point array t.
(2) Call InitO in GAPAK, for the integer segment, and randomly general an integer
chromosome close to the starting point st(l); for the floating-point segment, randomly
generate a floating-point chromosome close to the starting point st(2).
(3) Call evalcnO which calls evalO in GATST to calculate th chromosome's fitness
value, best-fitness, worst-fitness, average-fitness; store nElite most fit chromosome the global array fitsO. The most fit chromosome has the minimum fitness value. maximum problem such as Knapsack problems needs adjustment at this stage.)
(4) evalO calls the user-defined funcO to calculate the fitnes value.
Step 3: Running GAPAK for GA pecific subroutln s
(1) Call SelectO to select which chromosome to tay. According to roul tte selection method, the better fit chromosome has more chance to stay (but not guarantee stay). If a chromosome is selected to stay in the population, no more actions n ed done in SelectO. If a chromosome is not chosen to stay, it will be out of th population,
and then a new chromosome will be generated randomly. Each chromosome 37
population is checked whether it will tay in th population or not. JectO will stop the number of chromosomes select d to stay equal to the numb r of population size.
(2) Call CroverO
First randomly check a chromosome to see if it is within the crossover rate or not. randomly pick two parents and call the alpha-beta eros over subrolLtine crsIABO crsFABO respectively.
(3) Call MutateO
First randomly check a chromosome to see if it is within the mutation rate or not. randomly decide the mutation point and call the mutation subroutine MutIPLO MutFPLO respectively.
(4) Call EvalcnO which calls litO
nElite most fit chromosomes are stored in fitO array. lit chromo omes in a generation
will be compared, and replaced by nElite most fit chromosomes saved from generation.
Step 4: In GAPAK general package, redo EvalcnO which calls valO based on the generated chromosomes.
Loop step 3 and step 4 until the predefined maximum number of generations is exceeded.
38
Step 5: Print out the best chromosome and its fitn alu ith GAP K ubroutine
shbest().
3.2.5 Running the package
Compiling and running GAPAK/GATST package.
(1) Set up the FORTRAN environment
- Download the g77 FORTRAN Compiler from the following w bsite
http://www.geocities.com/Athens/Olympus/5 564/
- Unzip the package to a folder named c:\g77
- Set environment variables by running 77.bat
- Or Set up the following environment manually
PATH=c:\g77\bin;%PATH%
SET LffiRARY_PATH- :\g77\Jib
(2) Build GATST package
- Copy the source code gapak.fto c:\g77
- Build the FORTRAN package by running gat.bat
- Or manually build by the following command
g77 -c gatst.f
ar -r gatst.a gatst.o
39
(3) Build GAPAK program
- Copy the source cod gapak.fto c:\g77
- Build th FORTRA package by running gap.bat
- Or manually build by the following command
g77 gapak.f -0 gatst.exe gatst.a
(4) To run the program, type "gatst"
(5) Prepare the GA configuration with c:\g77\ga.inp to get another test case to run.
3.2.6 Two special testing problems
(1) Dealing with the 0/1 knapsack problem
The 0/1 knapsack problem is a test case of the pure bit string mode. Ext mal arrays weights of sacks and valu.es of sacks n ed to be load d from LnplltO. hromo om strings) are randomly generat d in 1J1itO. The fitness [un tion lIncO can calculale weight and the value of every chromosome. For example, in a 0/1 knap ack problem
there are five sacks. Their weights and values are in Table 3-2. lIppose a chrom is 01101, which mean item numbers 2, 3 and 5 WIll be chosen. From the weight value table, the weight of the chromosome 01101 is 20 + 16 + 6 = 42, the value chromosome is 10 + 200 + 80 = 290.
40
Table 3-2 Weight and value infonnation of a knapsack problem
index weight valu
1 25 100
2 20 10
3 16 200
4 10 60
5 6 80
In the Oil knapsack problem, the capacity and the sum of value are two criteria to optimized result. The capacity of the best solution must be in the range of the capacity
given, and the value of the best solution must be as large as possible. The capacity defined as half the sum of the weights. Since the g n rIGA package only proce minimizing problem, while the knapsack problem is a maximizing problem, there conversion between the maximizing problem and th minimizing problem in Figure 3-3 shows the fitness fimction and converting a maximizing problem minimizing problem in FORTRAN 77.
41
c Sum the wights and profits
c
wt=O.OdO
val=O.OdO
do 63 i=l,nint(nvar)
wt=wt+bitSts(ichrom,l,i)*xvar(i)
val=val+bitSts(ichrorn,l,i)*yvar(i)
63 continue
c
c Over capacity, drop,this solution, set the fit to minimum
c
if(wt>cap) then
val=sum
else
c
c Record the profits, the better value the less val to fit
c the minimizing algorithm to other samples
c
val=sum-val
endif
return
end
Figure 3-3 Source code of the fitness function of the knapsack problem
42
(2) D aling with the TSP problem
The TSP problem is a test cas of th re tri t d integer mod [25] [26). The e array of city x-location and y-Iocation n d to be load d from inputO. A new variable nUniq is passed to GAPAK to control th initO to g nerate only non-duplicat
chromosomes. The fitness ftffiction funcO rechecks the uniquenes of th chromosome
because the uniqueness status might be changed after GA operations such as crossover
and mutation. If a chromosome is found containing a duplicated number, chromosome will be assigned maximum fitness value which makes it having the chance to be selected in the next generation. For example, in a 5-city TSP problem, chromosome is inspected as 12234 which contains duplicated number 2, chromosome is nonsense for the TSP problem definition, so it will be assigned large fitness value, i.e. 99999999. The bigger the fitness value, the less chance chromosome will be selected. Since chromosome 12234 bas fitness value 99999999, has very little chance to stay in the population.
43
H PT RI
TE T PROBLEM
For the test problems, six test cases will be used. The following ctions d ribe definitions of test problems.
4. I Rosenbrock function
The Rosenbrock function is a test function to minimize
In my test case sets, there are only two parameters XI and X2, which are in th range 3], to be tested, and the first generation is generated from the starting point (x10, X20) 1.0). There are many varieties of standard Rosenbrock ftmctions, and three different
style functions will be tested.
(1) Standard Rosenbrock function
Find the minimum ofF(x) = 100*(x2 - X1 2/ + (XI _1)2, XI and X2 in [-3, J,
(XIO, X20) = (-1.2 1.0). The value ofx\ and X2 is (1.0, 1.0) to minimize F(x). Two modes are used for this standard Rosenbrock Function. The first one combination mode, in which XI is an integer and X2 is floating-point. The second is to test the pllTe floating-point mode, in which XI and X2 are both floating values.
44
(X 10, X20) = (-1. , 1.0). x I is an tnt grand 2 is floatin -p int. he alu 0 I and is (1.0, 1.0) to minimiz In thi funclion, th p rti 1 d ri ali s are continuous but have finite discontinuiti s.
(3) Hollow-ground Rosenbrock function
Find the minimum ofF(x) = 100 * ~I x 2 - x; I + IXI -11 ,XI and X2 in [- ,3]
(XIO, X20) = (-1.2,1.0). XI is an integer and X2 is floaling-p int. The value ofx, and is (1.0, 1.0) to minimize (x). In this function, the partial den alives have infinite
discontinuities.
4.2 xTX problem
1\
The xTx problem is to minimize F(x) = LX~ , n is a po ili inl g r. In my 1\
problem sets, F(x) = LX~ , n = 5. When (XI X2 X3 X4 xs) i (00 0 0 0), F(x) 11a mInImUm value. Two test cases are us d for this function. h first one is combination mode, in which x I, X2 and X3 are integer , and X4 and Xs are floating-point.
The second one is to test the pure floating-point mode, in which XI, X2, and Xs are all floating-point.
45
4.3 011 Knapsack problem
There is a set of items each with a weight and a value. The knap ack problem detennine which items to put in a collection so that the total weight i Ie s than given weight limit and the total value is as large as possible. Th general knapsack
problem is an NP-hard problem so it can be sol ed comparatively well by algorithms since an exact solution will be ery slow. The 0/1 knapsack problem r the number of each item to zero or one. It is a good bit string test problem for package.
4.4 Travehng Salesman Problem (TSP)
TSP is an optimization problem in graph theory, in which the nodes of a graph connected by directed edges. The weight of an edge is the distance between two The problem is to fmd a path that vi its each city once, r tum to th tarting city, minimizes the distance traveled. TSP is al 0 a NP-hard problem, which can be olv genetic algorithms. Different from other t st problems, TSP is a restricted encoding problem because no duplicates are aHowed during any g 11 ratioll.
46
RAPTER
RE LT
This chapter will list the results of all the test problem d cribed in hapt r IV.
5.1 Rosenbrock function
Four test problems are done in this test category.
(1) Standard Rosenbrock function with two floating-point input XI and X2 in the range
[-3, 3] is generated from the starting-point (-1.2 1.0). The minimum function
value is 0.0 when both XI and X2 are 1.0.
Table 5-1 The result of standard Rosenbrock function with two floating-points input
Number of generations Th b t chromosome The fitn ss alue
5 -1.1121152 1.2470301 4.47149567
10 -1.1121152 1.247030 I 4.47149567
50 -1.1121152 1.2470301 4.47149567
100 1.7288760 2.8462620 2.56902285
300 1.0625144 1.0111968 1.39017932
500 1.0625144 1.0111968 1.39017932
1000 0.6749835 0.4540560 0.105874961
47
From the above table e can e th result ar not ood. h fl ating point cro and mutation methods of Haupt and Haupt may b a problem and oth r m thods should
be tried for floating point ariables.
(2) Standard Rosenbrock function with a mixed input sty]. I i an int ger and floating-point in the range [-3, 3], generated from th star6ng-point (-1.2 The minimum function value is 0.0 when both XI and X2 are I. .
Table 5-2 The result of standard Rosenbrock function with one integer input and floating-point input
Number of generations The best chromosome The fitn ss value
15 -1 1.2470301 10.1023873
10 -1 1.2470301 10.1023873
50 -1 1.0325535 4.10597304
100 -1 1.0325535 4.10597304
200 1 0.9288640 0.506032661
500 11.0111968 0.0125367552
1000 11.0111968 0.0125367552
From the above table, we can see that convergence is achiev d in thi combinational
input for standard Rosenbrock function. The more the number of generations, the the result will be. At the 1000th generation, the fitness value of the best chromosome,
0.0125367552, is near optimal alue.
48
(3) Flat-ground Rosenbrock function ith ami d input tyl . Xl is an integer is floating-point in the rang [-3 3] g n rat d from th starting-point (- 1.2 The minimum function alu is 0.0 wh n both I and X ar 1.0.
Table 5-3 The result of flat-ground Rosenbrock function with one integer input one floati.ng-point input
Number of generations The best chromosome The titne s value
5 -1 1.2470301 26.7030105
10 -1 1.2470301 26.7030105
50 0-0.0469185 5.69185
100 o-0.0469185 5.69185
200 0-0.0469185 5.69185
500 1 0.9998685 0.01315
1000 1 0.9998685 0.01315
From the above tables, we can see that convergence is achieved in thi combinational
input for flat-ground Rosenbrock function. The more the I1lLmber of generations, better the result will be. At th 1000th generation, the fitn value of the chromosome, 0.01315, is near optimal val ue.
(4) Hollow-ground Rosenbrock function with a mixed input style, XI is an integ X2 is floating-point in the range [-3, 3], is generated from the starting-point 1.0). The minimum function value is 0.0 when both Xl and X2 are 1.0. ,
49
Table 5-4 The result of hollo - round Ro nbro k function ith one int g r and on floating-point input
Number of generations The b st chromosome Th fitnes alu
5 -1 1.2470301 51.1163367
10 -1 1.2470301 51.1163367
50 a -0.1464075 39.263233
100 0-0.0112076 11.5865849
200 0-0.0112076 11.5865849
500 0-0.0112076 11.5865849
1000 o-0.0052590 8.2518963
From the above table, we can see the results are bad. This GA package does not well for the hollow-ground Rosenbrock function. The floating point methods of and Haupt may be at fault.
5.2 xTx problem
(l) The pure floating-point mode is lested, where x), X2 x , X4 and Xs are all floatingpoint
values.
50
Table 5-5 The result of x problem of 5f1oatinb -point ariabl s
#Gen The best chromosome Fit value
5 -0.51631801.0317525 1.2240150 -0.0633315 -0.1464075 2.85475625
50 0.0985185 0.1960755 -0.4363635 -0.3637860 -0.4512285 0.574512014
100 0.0985185 0.1960755 -0.4363635 -0.3637860 -0.4512285 0.574512014
500 0.09851850.1960755 -0.4363635 -0.3637860 -0.4512285 0.574512014
1000 -0.33818100.0190500 -0.3376215 -0.1021905 0.1602570 0.264842773
From the above results of pure floating-point xTx problem, we can see the resl11ts are At 1000th generation, the fitness value of the best chromosome is 0.264842773 which not very close to the optimum O. This GA package does not work well for all floatingpoint
mUlti-parameters. Again, the floating point methods of Haupt and Haupt may fault.
(2) The combination mode is tested, where xI, X2 and x are integers, X4 and floating-point values.
51
Tabl.e 5-6 The result of xTx problem of 3 jnte er
#Gen The best chromosome
5 0000.4752765 -0.1026180
50 o0 0 0.0500565 0.0225795
100 0000.0500565 0.0225795
500 o0 0 0.0500565 0.0225795
1000 0000.0500565 0.0225795
ariables and 2 floating-point ariables
Fit alue
0.236418205
0.00301548701
0.00301548701
0.00301548701
0.00301548701
From the above results of the combinational xTx problem we can see the convergence achieved. At 1000lh generation, the fitness value of the best chromosome is close optimum O. This GA package works better for the combinational multi-parameters for all floating-point mUlti-parameters.
5.3 011 Knapsack problem
The test data in Table 5-7 is a well-known 011 knapsack te t data set.
Table 5-7 The test c1ata of a 011 knap ack problem
# Item Weight Value
1 100 40
2 50 35
3 45 18
4 20 4
5 10 10
6 5 2 ,
52
Table 5- The r ult of a /l knap ck probl m
# ofGen Best chromosom R tum d alu R al alu Total ight
5 011100 52 57 115
10 011011 44 65 110
50 011011 44 65 110
100 011011 44 65 110
Since the knapsack problem is a maximization problem th r is a conv r ion for knapsack problem to fit the general GA package designed for minimizing probl m5. the output file, the returned value is not the real value of total s lected items. Th value has the following calculation.
Capacity = sum of Weights / 2 = 115
Sum = sum of value = 109
Real value = Sum - Returned valu
From the result, we can see that convergence is achieved. Aft r nly 10 generations optimum is found.
5.4 TSP Problem
The following test data is a well-known TSP problem test data set.
53
Tabl 5-9 The t t data of a T P problem
City inde X-location V-location
I 5 5
2 -6 -8
3 3 3
4 1 7
5 6 2
6 -I 4
7 0 -5
8 4 5
9 -4 -3
Table 5-10 The result of a TSP problem
# of generations The best chromo om Th b t fitness
5 729645813 47.06238
50 729645813 47.06238
100 729648135 45.2355045
500 729648135 45.2355045
From the above result, we can see that convergence is achieved and the optimum value
45.2355045, which is known as the optimal value of this test data, is found.
54
HAPTER Vl
FUTURE WORK
The genetic algorithm is one of best methods for approximate solution of optimization
problems. The general genetic algorithm package designed in this thesis uses Goldberg simple genetic algorithm [13]. It ean process four different input modes, pure bit strings
pure integers, pure floating-point values and any combination of the above three modes one chromosome. This package uses roulette wh 1 I etion proportion I to the fitn value of chromosomes. The ero so er method u ed for the bit tling representation three options, single point crossoer, doub] point cros over and random cro ver; crossover method used for the integer and floating-point representations is Haupt Haupt's crossover for real value parameter [23]. Th bit string mod u e a simple
mutation way that randomly flip bits; the int grand (l ating-point 111 dum Haupt and Haupt's mutation for r al valu paramel r [2]. n g n ti algorithm
techniqu used in thi general package i eliti 111 whi h k P som f m Clll·OInO omes for the next gen ralion. he 1 st I' suit of this package a convergence and are mostly sati [actolY 0 improv th pcrformance, ther might some aspects to be con ider d.
(L) If some chromosome appear (0 be same In a generation, it means that population is tending to convergence. If all chromos mes arc equal, we can the whole population has cOllverg d. The eo~vergenc means the 55
chromo om i aLm t a hi d. T a hi n th r a m th ch ck th dupli at and d I,et th m.
(2) Profe sor Gary en (0 E ) ha a method t impro e th p rforman genetic algOIitlun, whicJ1 i to modify th p pulati n iz. During th g generations, the numb r of chromosome i lI1cr a d fir t, and th 11 d cr a one. This method might be tried in my packaee in th future.
(3) GAlib is a r latively g neral GA packag. orne of its feature could b tried my GA package, such as difti rent algorithm options --- the steady-state genetic
algorithm and the incremental genetic algorithm.
(4) For the election op ration, th re are 111 ny hoice, SLI h a r ulctl wh sel etioll, stochastic univer al sampling, rank sel cti n, Boltzmann sel clion,
steady- tate s lection, tournament selection, etc. us d a rank selection.
CalTOU s FORTRA package used a t urnamenl selection. My A package a roulette wheel selection. Different selection methods e ufd be tri d t test p rfomlance.
(5) Th genetic algorithm is just one of the eood approx imate meth ds to d al optimization problem. imulated annealing, volutionary computation 56
parti I swann ptimizati d m til mp n n uJd b t n th genetic algorithm and th r m th d
57
[lJ g. h ppro h, J E ignal Pro e . . 1, ~ 199
[2} La: leT E.L., L nstra J.' hID d. Tit Tr Salesman Pr fem John V it
[3] Corm n T.H. serson, Ri est R. ., Infrodl liol1 to Cambridg, A. 2 L
[4] yala, FJ. and tebbins, G.L. The olution of D . lUi m, ientific m pp. -" Jul , 198-.
[5] Holland .H.. daptation in J atural andrtijicial m e ity f Press, Ann r, 19 -. ec nd editi n: IT Pr s t
[6] Obi ko htlpJlcs. felk.c t.
[71 right H. Gen tic AI oritbms for Real Param t Optimization in R lins, (00..). Gund. tions of n tic Algorithms J pp.20S-2Iorgan Kaufmann,. an aliibrnia, 1 I.
[8] Whitley L. D., (ed.), Foundation 0 Gen tic Jgorlthm 2, Morgan K ufmann, Mateo, CA, 1993.
[9] Chambers, L., (ed.), Genetic Algorithms, Application " V 1. I, R Pr s ew 1995.
[10] Fogel, D,B., (ed.), Evolutionary omputation: The Fos il Record, Wil y-Computer Society Pr, March, 2001.
[11] Rechenberg, L, Cybernetic Solution Path of an Exp rimental Problem Mini Aviation, Royal Aircraft Establishment (U,K.), 196'5.
[12] Rosenberg, R.S., Simulation of Genetic Population' with Bio hemical Properlie Ph.D. Dissertation, University of Michigan, Ann Arbor, 1967.
[13] Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning,
Addison-Wesley:Reading, MA, 1989.
[14] Mitchell, M., An In.troduction to Genetic Algorithm, the MIT Press, ambridge
Massachusetts; London England, 1999.
[15]GALIB,htt ://lancet.mit.edu/ a
58
[16] Da i . Handbook ofGen li Algorithm an trand R inh ld [17] GE E IS, do\! nload from =h=ttp<=..::c...:..II-'-'-'-'-'-'-'-=:':"O:"":=.:...,J..:.~~~~~~
[18] Baker, J.E. Adaptive sel ction m thods for gen ti algorithms In
J.(ed.), Proceedings of the Fir lInt mational onfi r" on 11 ti Al
Their Applications pp.l 01-111 Lawrence Erlbaum A ociat s, Hi 11 dale
[19] Carroll, D.L., FORTRA Gen tic Algorithm (GA) Dri r,
http://cuaerospace.comlcanolVoa.html 20 1.
[20] News group: comp.ai.gen tic A Guide to Frequently A ked Qu stions,
http://www-2.cs,cmu.edu/Groups/AIlhtml/faq laj/g netic/part6/fag-d c-l.html
[21] Michatewicz, Z., Genetic Algorithm + Data Stru ture = Evolution Programs
Springer-Verlag, NY, 1996.
[22] Adewuya, A.A., New Methods in Genetic Search with Real-Valu d hromosom Master's thesis, Massachusetts Institute of technology, Cambridg , 1996.
[23] Haupt, R.L. and Haupt S.E., Practical Genetic Algorithms, John Wiley & 1998.
[24] Aarts, E.H.L. and Lenstra, J.K., (ed.), Local search in Combinatorial Optimization
John Wiley, Chichester, UK, 1995.
[25] Goldberg, D.E. and ingl, R., All les, Loci and the raveling at m n Probl Proceedings ofthe Second International onferen eon n li Al orilhrns,
Lawrence Erlbaum Associates, Mahwah, NJ, 1985.
[26] Grefenstette, J., Gopal, R., Rosmaita, R. and ucht, D. enetic algorithms traveling salesman problem, Proceedings of the Se ond International onfi r Genetic Algorithms, Lawrence Erlbaum Associates, Mahwah, NJ, 1985.
59
APP NOI n ral pac ag AP
c#N# NA'/1#.;' NUN N,~,¥ N?!ft#//N';'NNliN N/INN f.!####t4t1t1#N1I'f/ NJlNb:// //Nt;' N/fA'11 1/HI/Nit::,;'//;;//1/1//1////UN 1/
c
program gapak
c
c general GA subroutine packag
c
c Ting Zhu
c
c###/INNNN######Ift!II f:iNNN.1'1/ j~ fi' NgUNN#t!!lf!N#NNfl h'N#NN//##/I/I h'##R'/NI###h'N#1/ /lItN h' //#hW//
c
c###############AW//NNN.¥,'fNtt;\, !/#N lIN Nh'##//# fliNt gN//;\'##tNlflltltt!## N#;\';\'//1//IN 1/.MAWR'N
c Input variable definitions:
c
c nchrom the number of chromosome
c fit an array to save fitne s value of every chromosome
c bstfit the fitness value of the chromo orne v ith be t fitne s·
c wstfit the fitness value of the chromo orne v ith worst fitne
c avgfit average fi tness value of the chromosomes in a generation
c nGray gray coding flag
c o disable gray coding
c 1 enable gray coding
c mrate the mutation probability rate b tween 0 and 1
c crate the crossover probability rate between 0 and I
cnDbg debug flag
c o 0 debug
c 1 limited debug info
c 2 detailed debug info
c ctype rossover Type for bit tring n oding
c o ingle point cr . over default)
c 1 double cros over
c 2 random crossover
c 3 floating point cro saver
c nUniq chromosome unique flag
c o chromo orne doe not n ed to b uniqu
c I chromosome must be uni.que (for example T P city mu t unique)
c nElit number of most fit chromosom to tay
c
c#fliNJIf#/f#//N/iN //i,';\, ,'/NUN// NN#tI// Nit,;'N;\,t,'Ni/######lIltNgNOliNN##N/I###// // N/?###IINJ/tINI/I,'!i
c GATST Subroutines: (provided by caller)
c
c input load configuration infon11ation
c eval evaluates the fitne of each chromo ome
c
c Subroutines:
c
c gray gray code transforming 011 integer
c degray degray cod tran forming on integer
c i2b convert integer to bit-string
c b2i ~onvert bit-string to integer
c init InJtlahze th fIT t generation of chromosome
c select perfoml selection for next round
60
c crover p rfonns cr so er
c rslAB crosso er for Integ r
c rsFAB ero sover for Floating point
c rsBit ero over for bit tring
c mutate perfomls mutation
c MutIPL Integer mutation ba . d on p 01 el ctioll
c MutFPL Floating point mutation ba d on pool I ction
c elit retains the best solution from last g .n rati n
c evalcn evaluates the fitne of each chromo ome
c timc user defmed evaluation function, u e tandard Ro enbrock
e function as a sa.mple
c esol1 combsort
e dump shows the debugging infomlation
c shbest prints the b st solution
c ran3 the random number generator subroutine
c
e
c####/!tttl#lii/#######fI//NNN#:###########f!/II/iI/<IIIf/##i/f////llltI#NN###/t//f/NNNIINNiltI#####
c
c Main entrance
c
implicit real*8 (a-h,o-z)
save
e
parameter (ctmax=80 popmax=30,vamlax=1O,bitmax=lO,LP=6)
c
integer maxgen,nGray
integer nDbg,nchrom,etype.nStart,bits,bitSts,ints
integer ngen,nBitSt,lenStr,nIntgr,nFloat 11Uniq,nElit
c
conIDlon / g6 / nDbg,nchron1.,ctype,n tart,maxg n,n niq,n lit
c
call input
call init
call eva1cn
if(nDbg.gt.O) then
write(LP,*) 'generation*: I'
call shbest
endif
c
c Now we are in GA operation loop until we reache the
c maximum generation limit
c
do 1 ngen=2,maxgen
call select
call crover
call mutate
call eva1cn
if(nDbg.gt.O) then
write(LP,*) 'generation ** :',ngen
call shbest
endif
continue
61
c
c Print the final re ult itll be t solULi n
c
writ (LP *) 'total generation:' ngen-I
call hbe t
stop
end
cN####N#######UNh'###########liNUN##U#######ll##u##unnnnnnUUNNUU##nUnuuu#u#
subroutine gray(i hrom,idx)
c
c This subroutine does gray encoding to Integer
c Input
c i hrom index of chromosom
c idx index of integer s gment in chromosome
c Jmplementation:
c Integer is converted to bit string array bit 0,
c bitsO does the gray encoding then convert back to
c integer
c
cft ft #tillItI,' h'IV tiff!!t!N##f:I:####I!#....NUN N//11' t/NNflN tJff## N//tiN N//NNNt.'NUN/IN //// Nil Ng ,'f#I/N:nWNtI##
c
parameter (ctmax=80,popmax=30,vannax=1O,bitmax= IO,LP=6)
c
integer nBitSt,lenStr,nIntgr.nFloat,llLimiL dLimit,nGray
integer bits,bitSts,ints,tOlp k
c
common / g5 / bits(ctmax)
common / ggl/ bitSts(popmax,varmax,bitmax),ints(popmax,varmax)
common / gg2/ nBitSt,len tr nIntgr,nFloat,uLirnit,d imit n ray
ittnDbg.gt.O) then
write (LP,*) 'gray'
endif
c
c Convert integer to bit string
c
call i2b(ints(iChrom,idx),lenStr)
c
c Gray encoding sit string in working array bits
,c
tmp=O
do II 1 k= 1,lenStr
if(bits(k).eq.tmp) then
tmp=bits(k)
bits(k)=O
el e
tmp=bits(k)
bits(k)=l
endif
111 continue
c
convert back to int ger
c
62
call b2i(inl (i hrom idx I n tr)
r tum
end
c##UUU##UNUNUff##UUNff#U####HK########NU#######u#nuu#########fi##ffU#UU#U#
c
c Thi subroutine doe degray ncoding to Lnteg r
c Input:
c i hrom index of chromosome
c idx index of integer egm nt in chromo om
c Implementation:
c Integer is converted to bit string array bitsO
c bitsO does the degray encoding then convert back to
c integer
c
c###########################flfI!I#IINIIII#fftlNllllllfJNffN##tlllli#NIiNNIIII##iI###fJiI#####
c
parameter (ctmax=80,popmax=30 varmax=10 bitmax=10 LP=6)
c
integer nBitSt,lenStr,nIntgr.nFloat,uLimit,dLimit,nGray
integer bits bitSts,ints,tmp,k
c
common I g5 I bits(ctmax)
common / ggl/ bitSts(popmax,vannax,bitmax).ints(popmax,vannax)
common I gg2/ nBitSt,lenStr nlntgr,nFloat,uLimit,dLimit nGray
c
if(nDbg.gt.O) then
write (LP, *) 'degray'
endif
c
convert integer to Binary stream
c
call i2b(ints(iChrom,idx),len tr)
c
c Degray Encoding Binary stream
c
tmp=O
do] 12 k=l,maxbit
if(bits(k).eq.l) then
bits(k)=I-tmp
ele
bits(k)=tmp
endif
tmp=bit (k)
112 continue
c
convert back to integer
c
call b2i(ints(iChrom,idx),lenStr)
return
end
c#####NU#####u#n#u############U#HU###U#U##U#UU#######UffN######UflUNU##Nff#
subroutine i2b(i LnLen)
63
c
c Thi ubroutine conv rt int g r to bit tring
c Input:
c i I : input integer
c nL n: bit Iring I n th
c Output:
c bit: array to store th conv rted bit tring
c
c . otice:
c nLen ha to be proper length bit array an be corrupted
c value if nLen is too small because the ign bit bit (1
c is overwritten
c
c#######IIIItfIi' tV tilt // tIN#II it tJ1/1;'N// Jt ff fill It IIN#till11 11Nf!tllt!N!IIIWt/tItSt/NNlWItNl tnt It ##########
c
implicit real*8 (a-h,o-z)
save
c
parameter (ctmax=80, LP=6)
c
integer nDbg,nGray,nchrom,ctype,nStart,maxgen
integer bits,n,i,t,i 1,nLen,n niq,nElit
c
common / g6 / nDbg,nchrom,ctype,nStart maxgen,nUniq,nElit
common / g5 / bits(ctmax)
c
if(nDbg.gt.O) then
write(LP * 'i2b'
endif
c
c Po itive integer
c
if(i l.ge.O) then
t=i 1
n=nLen
do 101 i=l,n-l
bits(n+ l-i)=mod(t,2)
t=tI2
101 continue
bit (1)=0
else
c
c egative integer
c
n=nLen
t=2**(n-l)+il
do 102 i= I ,0-1
bits(n+ l-i)=mod(t,2)
t=tI2
102 continue
bit (l)=1
endif
if(nDbg.eq.2) then
64
write(LP *) i 1
do 103 i=I,nLen
write(LP,*) bits i
103 continue
endif
rehlffi
end
c
c###HUUN#####N##U#U####U#####KNN#N#nKU###U####UN######U########UU##UU###
subroutine b2i(i l,nLen)
c
c This subroutine convert integer to bit tring
c Input:
c bits: array to store the converted bit tring
c nLen: bit string length
c Output:
c i I : input integer
c
c#######nNNfI /1#fll/tiN Nt,'NNNt/lillliNfI //fJ/oJIl tUlti tt#//#t,' /!NN#lfNN III"? Nlff:lN NUltt!NN/tA'N#I?/tNtlti /111#
c
implicit real *8 (a-h,o-z)
save
c
parameter (ctmax=80,LP=6)
c
integer bits,n,i,t,nUniq,nElit
integer nDbg,nGray,nchrom,ctype,nStart,maxgen
c
conunon / g6 / nDbg nchrom,ctype,nStart,maxgen,nUniq,nElit
conunon / g5 / bit (clmax)
c
if(nDbg.gt.O) then
write(LP,*) 'b2i'
endif
c
c Positive integer
c
if(bits(l).eq.O) then
0=0
do 104 i=2,nLen-1
n=n+bits(i)
n=n*2
104 continue
n=n+bits(i)
else
c
c egative integer
c
do 105 i=l,nLen
bits(i)= I-bits(i)
105 continue
n=O
do 106 i=2,nLen-1
65
n=n+bit i
n=n*2
106 continue
n=- n+bit (i)+ 1)
endif
c
c a ign to return alue
c
il=n
if(nDbg.eq.2) then
write(LP,*) i 1
endif
ret.urn
end
c
c#######NUN /;'#!/NI! UNNNt/A"AItit! fi/1///lI; t1 (¥/IN#(J##1I ##t1N h' NIIN,Yfflfti (I tJ!lN fiNN f( Nh'#j¥#A'##,;'NtlNtI
subroutine init.
c
c This subroutine randomly generates the first population of
c chromosome according to different encoding type
c
c######It#h'fI,;'#/ltJ/ifttltt#,;'I/,;'//###I##Ih'#NIINh'#III/It####IIIt#N#/tf1t!f1Nf/fJ#/INNNIt#h'h'f/#,;',;'tI#/i
c
implicit real*8 (a-h,m,o-z)
save
c
parameter (popmax=30,vamlax=lO,bitmax=IO,LP=6)
c
integer nDbg,nGray,nchrom,ctype,n tart,maxgen
integer bitSts,int ,uLimit,dLimit,ij k,n niq,nElit
integer nBitSt,len tr,nLntgr,nFJoat k2,rdllg
c
dotlble precision float fit,kl t,randl
c
common / gl / st(varmax)
common / g6 / nDbg,nchrom,ctyp ,n tart maxgen,n niq,n lit
common / ggl/ bitSts(popmax,vannax,bitmax) int (popmax,vannax)
common / gg2/ nBitSt,lenStr,nlntgr,nFloat,u imit,dLimil,n ray
common / gg3/ floats(popmax,varmax),fit(popmax)
c
c Debug Log
c
if(nDbg.gt.O) then
write(LP,*) 'lnit ',l1chrom
endif
c
c Reset the global fit number
c
fit(l1chrom+ 1)=9999
c
call ran3(idum,rand)
c
chromosome loop for the whole population
66
c
do 41 i=l 11 hrom
c h ck bit lOng part
c
da 42 j=l nBit t
c
c Randomly generate bit string array
c
do 43 k:=l, lenStr
call ran3(1 ,rand)
if(rand.It.O.5) then
bitSts(iJ,k)=O
else
bitSts(iJ,k)=l
endif
43 continue
42 continue
c
c Ch ck Integer part
c
do 44 j=1, nlntgr
if(nStart.eq.O) then
c
c Random generate between range
c
k=uLimit-dLimit
47 call ran3(1,rand)
ints(ij)=dLimit+nint(rand*k)
c
c Check whether the chromo ome is uniq
c
if(nUniq.eq.l.and.nlntgr.gt.l) Ih n
rdflg=O
do 46 k2=lj-l
if(int (i,k2).eq.ints(ij») then
rdflg=1
endif
46 continue
c
c Found duplicate, redo the init
c
if(rdflg.eq.l) gota 47
endif
else
c
c Random generate close to start value
c
call ran3(1 ,rand)
call ran3(1,randl)
ints(iJ)=nint(st(j)+rand*(rand 1-0.5 )
endif
c
67
c Gray 11 oding thi chromo Olll
c
iii nGray.eq.l) then
call gray(ij)
endif
44 continue
c
c Check Floating point part
c
do 45 j=l, nFloat
c
c Randomly generate between ranges
c Pick the next start point follow the integer'
c
k=nStart-nlntgr
if(k.eq.O) then
k1=uLirnit-dLimit
call ran3(l,rand)
floats(i,j)=dLimit+rand*k I
else
c
c Randomly generate close to start value
c
call ran3(1 ,rand)
call ran3(1,randl)
tart point
floats(i,j)=st(j+nlntgr)+rand*(rand 1-0.5)
endif
45 continue
41 continue
c
c Chromosome Loop
c
if(nDbg.eq.2) then
call dump
endif
end
c#f1/11/ f.?##tJ IINflN1/1/#fJN#I/#NNflN#/tNfl #tJ##?If/NflN// NNNh'##NNNN//fi/itlN#### (J r!##N Nf:lNN #1/ fJ Nil
subroutine select
c
c This subroutine perfomls select GA op ration with Roulelle Wh
c selection method
c
cHilli',;'1/#####(IN,;'##r'1(j N#tlli',M!!It 1111 ###//,;'NtJNtJtJlt f{ tJtJNittitJNf{##### #####NNt?Ni///h'//#NNh'##
c
implicit real*8 (a-h o-z)
save
c
parameter (ctmax=80,popmax=30,varmax= 10 bitmax= IO,LP=6)
c
integer nDbg nGray,nchrom,ctype,n tart,maxgen
integer bitSt ,ints,uLimit dLimit,n nig k2 rdflg
integer nBitSt,lenStr,nlntgr,nFloat,irand i,j,k,nElit
c
68
d uble pr i ion mrat crat al
doubl preci ion 1 ftC tmax
c
common / g2 / b tfit tfit a gfit mrat ,crat al
common / g6 / nDbg.nchrom ctyp n tart maxgen n niq n lit
common / ggl/ bit t (poprnax, armax,bitmax ,int (p pma , armax
common / gg2/ nBit t len tr nIntgr nFloat uLimit dLimit,n ray
cornmon / gg3/ float (popmax,vannax fit(p pma'
c
if(nDbg.gt.O) then
write(LP, *) 'select'
endif
if(nDbg.eq.2) then
write(LP, *) 'bstfit " bstfit
write(LP, *) 'w tfit " w tfit
write(LP, *) 'avgfit', avgfit
endif
c
c Chromosome loop for the whole population
c
do 11 i=1,nchrom
c
c Calculate factors, the better fitness get better chance
c to selected for the next round
c
if(nUniq.eq.l) then
factor={ (wstfit - avgfit)/(wstfit-bstfit»)**2
else
factor=«{wstfit - avgfit)/{wstfit-bstfit))**2)**2
endif
factor=factor*(w tfit-fit(i))/(w tfit-b tfit)
if(nDbg.eq.2) then
writ (LP, *) 'fit " fit(i)
write(LP, *) 'factor', factor
endif
c
choose which chromo orne can tay for the next round
c
call ran3(1,rand)
if(rand.lt.factor) then
c
c Lucky guy stay
c
if(nDbg.gt.O) then
write(LP *) 'chromosome',i,' stay'
endif
c
c Degray called in non-GA operation uch as val0, now before enter
c GA operation, we have to call Gray agam
c
do 16 j=l, nlntgr
if(nGray.eq.l) th n
call gray(ij)
69
ndif
16 continue
el e
c
c nlu ky guy re huffle
c
if(nDbg.gt.O) then
write(LP, *) 'chromo om I i,' re t alue'
endif
c
c Check bit string part
c
do 12j=l,nBitSt
c
c Random generate bit tring array
c
do 13 k= I, lenStr
call ran3(1,rand)
if(rand.lt.O.5) then
bitSts(ij,k)=O
else
bitSts(i,j,k)= 1
endif
13 continue
12 continue
c
c Check Integer part
c
do 14 j=l, nlntgr
c
c Random generate integ r b tween range
c
k=uLimit-dLimit
18 call ran3( 1,rand)
ints(i,j)=dLimit+nint(rand*k
c
c heck whether the chromosome is uniq
c
if(nUniq.eq.l.and.nlntgr.gt.l) then
rdflg=O
do 17 k2=lJ-l
if(int (i,k2 .eq.int (ij)) th n
rdflg=l
endif
17 continue
c
c Found duplicate, redo the init
c
if(rdflg.eq.l) goto 18
endif
c
c Gray encoding tm chromosome
c
70
if(nGray. q. 1) then
all gray(iJ)
endif
14 continue
c
c Check Floating point part
c
do 15 j=l, nFloat
c
c Random generate between ranges
c
k=uLimit-dLimit
call ran3(I,rand)
floats(iJ)=dLimi t+rand*k
15 continue
endif
11 continue
c
if(nDbg.eq.2) then
call dump
endif
return
end
c
c#####N//N NNN II tJflt/# NflA' ,;'###,'/1/tV /I/;'/I ##tINUN,;' #N!4NNtlNftJotIl##t/Nflt?h'N//1/N/INNNII k'N til/tV It
subroutine crover
c
c This subroutine perfonns crossover GA operation
c
cfJnUti tit/Iiti fitill/{ till fI Nt/#II !INNNN###################If/;,f;'tllt##1/####################
c
implicit real*8 (a-h,o-z)
save
c
parameter (popmax=30,varmax= 1O,bitmax= lO,LP=6)
c
integer nDbg,nchrom,ctype n tart,maxgen
integer iJ,irand 1,irand2,nUniq,nElit
c
common / g6 / nDbg,ncbrom,ctype,n tart,maxgen,nUniq,n lit
c
if(nDbg.gt.O) then
write(LP,*) 'crossover'
endif
c
chromosome Loop for tbe whole population
c
do 80 i= 1,nchrom
c
c heck if this chromo orne need crossov r with cross-over rate
c
call ran3(I,rand)
if(rand.lt.crate) then
71
c
c eed ro so er operation Fir t rand mI tw par nt
c
call ran3(l rand
irand 1=aint(rand*nchrom c+ 1
81 call ran3(I,rand)
irand2=aint(rand*nchrom)+ I
c
c Make sure we have two different chromo orne a our parent
c
if(irand l.eq.irand2) go to 81
if(nDbg.gt.O) then
write(LP,*) 'parent ',irandl,' ',irand2' cro ov r I
endif
c
c Bit string Crossover with three options
c
do 82j=1, nBit t
call CrsBit(i,irand 1,irand2)
82 continue
c
c Integer crossover with integer Alpha-Beta calculation
c
do 83 j=1 nIntgr
call CrsIAB(i,irandl ,irand2)
83 continue
c
c Floating point Crossover with float Alpha-Beta calculation
c
do 84 j= L, nFloat
call rsFAB(i,irand l,irand2)
84 continue
else
c
c No need Crossover operation, tay ~ r the next round
c
if(nDbg.gt.O) then
write(LP,*) 'not cro sover'
endif
endif
80 continue
c
c Chromosome Loop (end)
c
if(nDbg.eq.2) then
call dump
endif
return
end
cm#1I#hW,\'#N#//h'#t.'NI/Ii N###N,\'#,\',\' iN/til/lI/1,\'#/1 /iN N,\' tI,\'1/ IIN#l!i~N NNN#IINfJ MHii'Nh'1.'#t!f{lIlffllffl
subroutine CrsIAB iChrom, Pamtl Pam12)
c
c Thi subroutine perfonn cros over for integer crossov r
72
c ba ed on Ipha-beta calculation
c
c
Input:
i hrom: ind x of chr mo orne
c
c
Parntl : the fLr t par at chromo oll
Parnt2: the econd par nt chromo
le
om
c
c
Output:
Integer array intsO perf0n11ed cr 0 er operation
c
c!1N,\',\'fifJggflgff#####flflh'jW,WN#NNN,.,.g#N##::N,\',~N#tlffh',\'gNI/I?{,'h'f?tlllh'1/#//ff#l/#I#tt/h'MI####
c
implicit real*8 (a-h,m,o-z)
save
c
parameter (popmax=30.varmax=1O,bitmax=1O,LP=6)
c
integer nDbg,nGray,nchrom,ctyp ,nStart,maxgen
integer bitSts,ints,uLimit,dLimit,nUniq nElit
integer nBitSt,lenStr,nIntgr,nFloat k iChrom tmp,Pamtl Parnt2
c
double precision alpha,beta
c
common 1 g6 1 nDbg,nchrom,ctype,nStart maxgen n ruq nElit
conunon 1ggll bitSts(popmax,varmax,bitl11ax),int (popmax varmax)
common 1gg21 nBitSt,lenStr,nIntgr,nFloat,uLimit,dLimit,nGray
c
if(nDbg.eq.2) then
write(LP, *) 'CrsIAB'
elldif
c
c calculate alpha and beta value
c
alpha=O
call ran3(1,rand)
b ta=-alpha+rand*(l.OdO+alpha*2.0dO}
c
c Only two parts need to swap
c
if(nchrom.eq.2) then
trnp=aint(ints(iChrom,Parnt 1)*(l-b ta» ,
ints(iChrom,Parntl )=tmp+nint(ints(i hrom,Pamt2)*beta)
tmp=nint(int (iChrom,Parnt2)*(1-b ta )
ints(i hrom,Parnt2)=tmp+nint(int (i hrom,Pamtl )*b ta)
else
c
c More than two part • then elect the era ov r point
c
k=(nchrom+1)/2
~mp=nint(ints(k,Parnt 1)*( I-beta)+int (k,Pamt2)*beta)
111t (k,Pamt1)=tmp
trnp=nint(int (k,Parnt2)*(1-b ta)+ints(k,Parntl *b ta)
lI1ts(k,Pamt2)=tmp
tmp=ints(iChrom,Pamt1)
ints(iChrom,Parntl)=int (iChrom Parnt2)
73
int (i hrom,Parnt2 =tmp
endif
retum
end
clt//#// // NII /II!tItl IIII #h'!lN// NNUN //NNNNN#/1 //////liNN// //N#//NN//IJIl /IN,Y//NNtltI// ////S#A'N.YN////IiN/I//NI/
subroutine rsFAB(iChroOl, Pamt1 Parnt2)
c
c This subroutine perfonn cro over for floating point cr o r
c based on Alpha-beta calculation
c Input:
c iChrom: index of cbromosom
c Pamt 1: the first parent cbromosom
c Pamt2: the second parent chromosom
c Output:
c Floating array floatsO perfonned crossover operation
c
c################tINflNN.¥//t/ #U UNit j~ N#####################11 Nt/tiNflffl/ /tNN /lit It/,'Nh'ff ff
c
implicit real *8 (a-h.m,o-z)
save
c
parameter (popmax=30,varrnax= I O,bitmax=lO LP=6)
c
integer nDbg,nGraY,nchrom,ctype,nStart,maxgen
integer bitSts,ints,uLimit,dLirnit,nUniq,nElit
integer nFloat,irand,k,iChrom,Pamtl,Pamt2
c
double precision aIpha.beta,floats,fit tmp
c
common / g6 / nDbg nchrom,ctype,n tart,maxg n,n niq,n -Iii
common / gg3/ floats(popmax,varmax).fil(p pmax)
c
if(nDbg.eq.2) then
write(LP,*) 'CrsFAB'
endif
c
c calculate alpha and beta value
c
alpha=O
call ran3( 1,rand)
beta=-alpha+rand*(1.OdO+aJpha*2.OdO)
c
c Only two parts need to swap
c
if(nchrom.eq.2) then
tmp=floats(iChrom,Pamtl )*( I-beta)
floats(iChrom,Pamtl )=tmp+float (i hrom,Pamt2)*beta
tmp=floats(iChrom,Pamt2)*(1_beta)
floats(lChrom,Pamt2)=tmp+f1oat (i hrom,Parntl )*beta
else
c
c More than two parts, then select the crossover point
c
74
k=(nchrol11+ 1 12
float (k Pamt 1 =f1oat k Pamtl * 1- ta +f1 at k Pamt2 * ta
float k'Pamt2 =floats k,Pamt2 * I-b ta)+fl at k,Parntl *b ta
tmp=fl~at (i hrol11 Parotl)
floats(iChrom,Pamtl)=f1oats(i hrom Pamt2
float (i hrom Pamt2)=tmp
endif
return
end
c#####Nh'#tltV fJ#N,',' III;' NNNN#//N1/ //,¥ /IN// tltlN#NII#/ltlh!,;'NUN StY,;'NAt;;'//NN/fNNf:?N .rNA'1I#1Ih'N//N#//tlil
subroutine CrsBit(iChrom,Pamtl ,Parn(2)
c
c This subroutine perfonn bit string cros over with three options
c Input:
c iChrom: index of chromosome
c Pamt 1: the first parent chromosome
c Pamt2: the second parent chromosome
c ctype: crossover subtype
c Output:
c Bit string array bitStsO perfonned cros over operation
c
c##glJ tll/#####t/#N #h'//NA' ,vla:/;,,vA'j~ N,¥NlI#h!N#tlf/tJ //#//NitA' /::/Nfl //t/(/NNil,;'////fillS/;,N,¥//.;'1/#N,vA'.v g
c
implicit real*8 (a-h,m,o-z)
save
c
parameter (popma.x=30,varma.x=lO,bitmax=lO,LP=6)
c
integer nDbg,nGraY,nchrom,ctype nStart,maxgen
integer bitSt ,int ,uLimit,dLimit n niq nElit
integer nBitSt,Ien tr,nlntgr,nFloat,irand3,irand4
integer k,i hrom,Pamt 1,Parnt2
c·
common / g6 / nDbg,nchrom,ctyp· ,n taJt,maxgen,n niq,n lit
common / ggl/ bit ts(popmax,varrnax,bilmax),ints(popmax,varmax)
common / gg2/ nBitSt,len tr,nlntgr,nFloat,uLimit dLimit,n ray
c
c Switch by thI e type of cro over
c
if(ctype.eq.O) then
if(nDbg.eq.2) then
write(LP, *)' rsBit Single-era over'
endif
c
c Single point crossover, plit the old chromo ome and mix th parts
c Randomly pick one point to cross-over
c
call ranJ(l,rand)
irandJ=aint(rand*lenStr)+1
c
c Swap bits between two parents
c
do 87 k=irandJ,lenStr
75
tmp=bit t i hrom Pamt1 k
bit i hr m,Parnt I k ~bit t hr m,Pamt ,k
bit ts(i hr m Pamt2,k ==trnp
87 continue
c
else if(ctype.eq.l) then
if(nDbg.eq.2) th n
write(LP, *) I rsBit Doubl -cro over'
endif
c
c Double crossover, hoose two points and three parts
c left/right part from old parent· middle part xchang
c
call ran3( I ,rand)
irand3=aint(rand*lenStrl2)+ 1
85 call ran3( I ,rand)
irand4=aint(rand*(npar-irand3))+irand3+ I
c
c Make sure we have two different points
c
if(irand3 .eq. irand4) then
goto 85
endif
c
c Swap the middle parts
c
do 88 k=irand3+ 1,irand4-1
tmp=bitSts(iChrom,Pamt1,k)
bitSts(i hrom Pamtl ,k)=bit ts(i hrom.Pamt2,k)
bitSts(i hrom,Parnt2,k)=tmp
88 continue
c
else if(clype.eq.2) then
if(nDbg.eq.2) then
write(LP,*) I r Bit Random-cro over'
endif
c
c Random crossover
c randomly d cide the bit to exchange
c
do 89 k=1 ,lenStr
c
c random decide the swap bit
c
call ran3 (1 ,rand)
irand3=ajnt(rand*lenStr)+1
tmp=bitSts(iChrom,Pamt I ,irand3)
bltSts(~Chrom,Parnt 1,irand3)=bitSt (i hrom,Parnt2,irand3)
bit t.s(IChrom,Parnt2,irand3)=tmp
89 contmue
endif
return
end
c/';;liNN Nf/I'JIIII II NNNIINI1'i/Nf/NN//,;'#// N//N##tJI1NN!tfiilfillNI/IY1I,v!1/,' /fil/JA' /il/ /IIIA' //11//1/#########
subroutine mutate
c
c Thi ubroutine p rfonns mutate
c
c######IINNNNNN,\'!fNt.'#NNNNN//NNNN//#NNN#ttNNNN/;;;//##Nh'/t/IA'NNtlt.'//tttllftt/!h'N//t.'NfNf!It.'Nt.'#
c
implicit real*8 (a-h o-z)
save
c
parameter (popmax=30,varmax= I0 bitmax=10 LP=6)
c
integer nDbg,nGraY,nchrom,ctype,11 tart,maxgen
integer bitSts,ints,uLimit,dLimit,nUniq,nElit
integer nBitSt,lenStr,nlntgr,nFloat irand,iJ,k
c
double precision mrate,crate,bstfit,avgfit.wstfit,val
c
common / g2/ bstfit,wstfit,avgfit,mrate crate, aI
commOll / g6/ nDbg,nchrom,ctype,nStart,maxgen,nUnig nElit
common / ggl/ bitSts(popmax,vannax bitmax ,ints(popmax,vannax)
common / gg2/ nBitSt,lenStr,nIntgr,nFloat uLimit,dLimit,nGray
c
c Chromosome Loop for the entire population
c
do 71 i= l.nchrom
c
c Check if this chromosome need mutate with mutate rate
c
call ran3(l ,rand)
it~rand.lt.mrate) then
c
c Do mutate operation
c
if(nDbg.gt.O) then
write(LP,*) 'cbrosom ',i,' mutate'
endif
c
c Bit string mutate, randomly pick a position and flip the bi;
c
do 72j=l, nBitSt
call ran3(I,rand)
irand I=aint(rand*lenStr)+ 1
if(bit ts(iJ,irandl).eq.O) then
bitSts(iJ,irand 1)= I
else
bitSt (iJ,irand 1)=0
endif
72 continue
c
c Integer Mutate with integer Pool calculation
c
77
do 73 j= I , IlIntgr
call MutIPL(ij)
73 continue
c
c Floating point Mutate with float Pool calculation
c
do 74 j= I., nFloat
call Ml1tFPL(i,j)
74 continue
else
c
c No need Mutate operation, stay for the next round
c
if(nDbg.gt.O) then
write(LP, *) 'not mutate'
endif
endif
71 continue
c
c Chromosome Loop (start)
c
if(nDbg.eq.2) then
call dump
endif
return
end
c############N#/l#/il1fJIINH,'Ih'//N#:'INJlII##N,\'#!lNN####,\'NA'IINillI#i4'h'#N##tlfJ!I,\'NtlNh'h'!I#N
subroutine MutIPL(iChrom,idx)
c
c This subroutine perfonns integer mutation ba ed on Pool. ele tion
c Input:
c iChrom: index of chromosome
c idx: index of the integer s gment of the chromosome
c Output:
c Integer array intsO perfonned mutate op ration
c
c###########################!!Ni,' HIII!##########/Ih'//h'IIII#######,\'N#I!###########
c
implicit real*8 (a-h.o-z)
save
c
parameter (popmax=30,vannax=1O,bitmax= LO,LP=6)
c
integer nDbg,nchrom,ctype,nStartlnaxgen
integer bitSts,ints,irand,i,idx,min,max,nUniq,nElit
integer nBitSt,lenStr,nlntgr,nFloat,uLimit,dLimit,nGray
c
conunon / g6 / nDbg,nchrom,ctype,nStart,maxgen,nUniq,nElit
conunon / gg 1/ bitSts(popmax,vannax,bitmax),ints(popmax,varmax)
conunon / gg2/ nBitSt,lenStr,nlntgr,nFloat,uLimit,dLimit,nGray
c
if(nDbg.eq.2) then
write(LP, *) 'MutlPL'
78
endif
c
min=uLimit
max=dLimit
c
c Select proper pool from the chromo ome population
c
do 76 i=l,nchrom
if(int (i,idx).gLmax) then
max=ints(i,idx)
endif
if(ints(i,idx).le.min) then
min=ints(i,idx)
endif
76 continue
c
c ow we have the pool range for this population
c Randomly create a value in th pool to mutate
c
call ran3(l,rand)
ints(iChrom,idx)=nint«max-min)*rand)+min
return
end
eN /,' /1,;'1/ ##11#11######tillNh'Nh'NilN/lj~g Ng,¥ 1//1 UNHgtJ?I N/t Nt/NitSA',;'11'11/1//NNgNN# Sf,' NUNN//1/ N##
subroutine MutFPL(iCbrom,id .)
c
c This subroutine performs floating point mutation with Pool election
c Input:
c iChrom: index of chrom ome
c idx: index of the float segment of the chrom ome
c Output:
c Floating point array float 0 p rform d mutat operation
c
c###########tlN/lNNNtI#//t:#It,;'h'N//,;'N##NN###########//N#########################
c
implicit real*8 (a-h,o-z)
save
c
parameter (popmax=30,varmax=1 O,bitmax=l O,LP=6)
c
integer nDbg nchrom,ctype,n tart,maxg n
integer bitSt ,ints,uLirnit,dLimit,n ray,n niq,nElit
integer nBitSt,lenStr,nlntgr,nFloat,irand,i,idx
c
double precision floats fit,min max
c
common / g6 / nDbg nchrom,ctype,n tart,maxgen n niq,n lit
conmlon / gg2/ nBit t,len tr,nlntgr,nFloal,uLimit,dLimit,nGray
common / gg3/ floats(popmax, varmax),fit(popmax)
c
if(nDbg.eq.2) then
write(LP,*) 'MutFPL'
endif
79
c
min=uLimit
max=dLimit
c
c Select prop r pool from the chromo m populati n
c
do 75 i=l ,nchrom
if(floats(i,idx).gt.max) th n
max=floats(i,idx)
endif
if(floats(i,idx).le.min) then
min=floats(i,idx)
endif
75 continue
c
c Now we have the pool range for this population
c Randomly create a value in the pool to mutate
c
call ran3(l ,rand)
floats(iChrom,idx)=(max-min)*rand+rnin
return
end
c####NNNNNtI######ft##I/N//NNJ/N gNNlIh'#NN ;VllllmlNNII//##N#N#NNN##h'tJllN#t!####
subroutine evalcn
c
c This subroutine evaluates the fitness of each olution
c by calling user defined evaluation functions, call csort
c and elit to retain the most fit chromo orne from last generation
c
c The following value i pa d to lectO
c fit(i) fitness value of this chromo orne
c bstfit best fitness value of this population
c wstfit worst fitness value of thi population
c avgfit average fitness valu of this population
c
c################?flttt/;'?fIlA' /IN Ng/1//11#############################11/1####
c
implicit real *8 (a-h.o-z)
save
c
parameter (popmax=30,vannax=IO,bitmax=IO,LP=6)
c
integer nDbg,ncmom,ctype,n tart,maxgen n niq,nElit
integer i,bitSts,ints,jptr,k
integer nBitSt,lenStr,nlntgr,nFloat,uLimit,dLimit,nGrayJ
c
double precision floats
double precision fit
double precision sumfit,x 1,xl,x3 x4,x5
double precision bstfit,avgfit,w tfit,rnrate,crat ,val
common / g2 / bstfit,wstfit,a gfit,mrate,crate,val
common / g6 / nDbg,nchrom,ctype,nStart,maxgen,nUniq nElit
80
common / g9 / jptr(popmax
common / ggl/ bit t (popma amlax bitmax ,int (p pma. nna,
common / gg2/ nBit t,len tr nlntgr nFloat,uLimit,dLimit n ra
common / gg3/ float (popmax, arnlax fit opmax.
c
if(nDbg.gt.O) then
v rite(LP,*) 'evalcn'
endif
c
c Reset the fit values for the ne\ generation
c
sumfit=O.OdO
bstfit=2**32
wstfit=-bstfit
avgfit=O..OdO
c
c Chromosome Loop for the entire population
c
do 31 i=l,nchrom
c
c on-GA operation has to call Degray to restore the
c original value before doing user-defined functions
c
do 32j=1, nlntgr
if(nGray.eq.l) then
call degray(i,j)
endif
32 continue
c
c Call u r-defined evalO function here
c
call eval(i)
c
c Save the bstfit,wstfit and the best index
c
fit(i)=val
if(fit(i).lt.bstfit) then
bstfit=fit(i)
endif
if(fit(i).gt. wstfit) then
wstfit=fit(i)
endif
sumfit=sumfit+fit(i)
c
c Init jptr array
c
jptr(i)=i
31 continue
c
calculate the avgfit
c
avgfit= umfitlnchrom
c
81
c Sort the fit(i) and get ne\) ord r ofjptr i arra
c
if(nElit.gt.l) then
call csort(nchrom)
endif
c
c Save the nElit chromo om by th ort d jptr array
c
do 37 k=1,nElit
c
c Save the best fitted chromsome as the nchrom+ 1chromosome
c
c Check the fitness value
c
if(fit(nchrom+k).gt.fit(jptr(k») then
c
c The bit string part
c
do 33 i=l, oBitSt
do 34 j=l, IenStT
bitStsCnchrom+k,ij)=bitSts(jptr(k),iJ)
34 continue
33 continue
c
c The integer part
c
do 35 i=l, nlntgr
ints nchrom+k,i)=ints(jptr(k),i)
35 continue
c
c The floating point part
c
do 36 i= I, nFloat
floats(nchrom+k,i)=floats(jptr(k),i)
36 continue
c
c The fitness number
c
fit(nchrom+k)=fit(jptr(k»
endif
37 continue
c
c Call Elit
c
call elit
return
end
c
cn##u#u##un#u#u#########,'lU#U######u#u######uun############u##U#n###H#
subroutine elit
c
c This ubroutine retains the be t olution of la t generation
c elit operates after evalO again, make llre nElit most fit chromo orne
82
c till in the n xt gen rati 11.
c
dUN..,;'I.' /If.;'IINil,;',;',;'NfWN....tN..NIi'/I tJ ../IIii' .....1////##,;'mIN,¥III/tiff/;'/11.'/1 I/Ii'Ilttlf//N........tr##ll##tlJI!I##NIt..MIt
c
implicit real*8 a-h o-z
save
c
parameter (popmax=30 vannax=l a,bilmax=1a LP=6)
c
integer nDbg nGraY,l1chrom,ctyp 11 tart maxgen
integer bitSts,int uLimit,dLim.it nrflg,n niq,n lit
integer nBitSt,lenStr,nlntgr nFloat,irand iJ k
c
double precision ll1fate crate,bstfit,avgfit,w tfit,val
c
conunon / g2 / bstfit,wstfit,avgfit mrate,crate,val
common / g6 / nDbg,nchrom,ctype,nStart,maxgen nUniq n lit
COIlUTIon / ggl/ bitSts(popmax,vannax bitmax),int (popmax,vannax)
cOI11fl1on / gg2/ nBitSt,lenStr,nlntgr,nFloat,uLimit dLimit,nGray
COll1fJ10n / gg3/ floats(popmax varmax),fit(popmax)
c
if(nDbg.gt.O) then
write(LP,*) 'elit'
endif
c
do 21 k=l,nElit
c
c The previous best fitted chromosome has lost
c restore it from our local copy
c
c The bit string part
c
do 22 i=l, oBit
do 23 j=l, len Ir
bitSts(k,iJ) = biISts(nchrom+k,iJ)
23 continue
22 continue
c
c The integer part
c
do 24 i=l, nlntgr
ints(k,i) = ints(llchrom+k,i)
24 continue
c
c The floating point part
c
do 25 i= I, nFloat
floats(k i) = floats(nchrom+k,i
25 continue
c
c The fitness number
c
fit(k)=fit(ncbrom+k)
83
21 contill ue
return
end
c
c#####h'//If i\'/itl#############tfr't.\'//NN###!NIIi'NN// /th'fttJNh'.vi\' /f.v#####N/li¥#N II' //.vNf/it
subroutine csoft(nl)
c
c Tills subroutine use cornbsort to sort an array fit by it
c length nl , jptr array has t11e sorted chromo ome index which
c is used by evalO to retain the nElit most fit chromosome for GAPAK u
c#h'NtI?/I/f1t1###tItIfj /i /IN // //#####tJJlII N// UN // NI/,;'#,vlliyItNN?I /I1ff.?#######tJ#N NII/,'NN11'111/#
c
implicit real *8 (a-h,o-z)
save
c
parameter (popmax=30,varmax=10,LP=6)
c
integer nDbg,nchrom,ctype,nStart maxgen,nUniq,nElit
integer n 1,gap,bOrder,nCompj ,jptr,ntmp
c
double precision temp
double preci. ion floats
double precision fit
double precision sfit(popmax)
c
common / g6 / nDbg,nchrom,ctype,nStart,maxgen,nUniq,nElit
common / g9 / jptr(popmax)
COIJUllOn / gg3/ floats(popmax,varmax),fit(popmax)
c
c init the temp array
c
gap =nl
if(nDbg.eq.2) then
write(LP, *) 'before c ort'
clo 108 j=l,nl
write(LP,*) jptrU)
108 continue
do 103 j=l,n I
sfit(j)=fit(j)
write(LP, *) sfit(j)
103 continue
endif
c
c Start the next pass.
c Reduce the gap length by a factor of SHRINK.
c
104 if(gap.ne.l.or.bOrder.eq.l) then
c
c Adjust for a new gap
c
gap = (gap*10)/l3
if(gap.eq.9.or.gap.eq.10) then
gap=ll
84
endif
if(gap.lt.l) then
gap=1
endif
c
c Set flag bOrder to detect any iat rchange .
c
bOrder = 0
do 105 j=l,nl-gap
nComp=j+gap
if(sfit(j).gt.sfit(nColl1p» then
c
c Switch pointer
c
ntmp=jptr(j)
jptr(j)=jptr(nComp)
jptr(nComp)=ntmp
c
c Two elements are out of order. Flip the flag
c and Interchange the two elements
c
bOrder=l
temp = sfit(j)
sfit(j) = sfit(nComp)
sfit(nComp) = temp
endif
105 continue
goto 104
endif
if(nDbg.eq.2) then
write(LP,*) 'after csort'
do 106 j=1 ,nl
write(LP,*) sfit(j)
106 continue
do 107 j=1 nl
write(LP,*) jptr(j)
107 continue
endif
retum
end
c######1i'1/N/it' N##1111II II,;' NN::N###II //i/ft#####tJNil /1 #I/###########J,',11tNIt1/t'N#lIN N#####
subroutine dump
c
c This subroutine show chromosome debugging infom1ation
c by dumping the BitSts, ints and floats array
c
cll#,;'1;'N/il;' /I IIJlUN,;'!/If11####,;'Nii /I1I!l#N//!! // NN######l1fJ II NNt' tV 1111Nt\' Nt\' t\'t/######f! Itiiii1/## l!f.?tI #
c
impli.cit real*8 (a-h,m,o-z)
save
c
parameter (popmax=30,varmax=1O bitmax=l 0,LP=6)
c
85
integer nDbg n ray,nchrom ctype,n tart,maxg n
integer bitSts,ints,uLimit dLimit,n niq,1 lit
integer nEit t,lenStr,nlntgr nFLoat ij k
c
double precision floats fit
c
common / g6 / nDbg,nchrom,ctype,n tart maxg n,n niq n lit
common / ggI/ bitSts(popmax,varmax bitmax) int (popmax,varmax)
common / gg2/ nBitSt,lel1. tr,nlntgr nFloat,uLimit,dLimit nGray
common / gg3/ floats(popmax,vannax),fit(popmax
c
c Chromosome Loop for the entire population
c
write(LP,*) 'dump'
do 51 i=l,nchrom+nElit
write(LP,*) 'chrom ',i
c
c Print bit string part
c
do 52 j=1, nBitSt
write(LP,*) 'bit-string-segment ',j
do 53 k=1, lenStr
write(LP,*) bitSts(i,j,k)
53 continue
52 continue
c
c Print integer part
c
do 54 j= I, nlntgr
write(LP,100) ints(ij)
54 continue
c
c Print Floating Point part
c
do 55 j=l, nFloat
write(LP,10 1) floats(ij)
55 continue
100 fonnat(' integer-segment',1x,i5)
101 format(' floating point-segment',1x,f8.2)
5\ continue
return
end
c###################h'N,¥f/N ..../lNf/,;'//Nh'N####!!f///N###### ....,','f1Nii....U/!,;'//N/lf/NUI?IJ#//NI/NII//
subroutine shbest
c
c This subroutine prints the best solution
c
cf/NNh'N ....#f/ItIt#f?Nt.'NtlfJI!NNh'f/,YNNN//Nh'#####/I,;WNItNI!#NNI/f/###Nf:lh'//t/####/lh't.'NU########
c
implicit real*8 (a-h,m,o-z)
save
c
parameter (popmax=3O,varrnax=1 O,bitmax=1 O,LP=6)
86
c
int ger nDbg nGraY,nchrom,ctyp n tart 111 gen
integer bit ls,ints,uLimit,dLimit n niq,nElit
integer nBit t len tr,nlntgr,nFloat,iJ
c
double precision floats fit
c
COITU110n / g6 / nDbg nchrom,ctype,n tart maxgen n niq n lit
common / ggl/ bitSts(popmax,varmax bitmax),int (popmax.,vannax)
common / gg2/ nBitSt,lenStr,nlntgr,nFloat,uLimit dLimit nGray
common / gg3/ floats(popmax,vannax),fit(popmax)
c
c Print bit string part
c
do 5 i=l, nBitSt
do 6 j=l, lenStr
write(LP,*) bitSts(nchrom+1,ij)
6 continue
5 continue
c
c Print integer part
c
do 7 i=l, nlntgr
write(LP,102) ints(nchrom+l,i)
7 continue
c
c Print floating point part
c
do 8 i=l,nFloat
write(LP,103) floats(nchrom+ 1,i)
8 continue
102 formatC' integer-segment', Ix,i5)
103 formatC' floating point-segment', lX,f15.7)
c
c Best fitness number
c
write(LP,*) 'best fitness value:', fit(nchrom+ I)
return
end
c
cN!!N#t!lJ####fJ N,\W0\' 0\' 0\'0\'o\'i/IIh'o\'IItNft/#//f,'h'!I!1##f;' 0\' iiNNNo\'N########/IIliINN 0\' mlt/MIN/!No\'o\'/,'/,'NN 0\'
subroutine ran3(idum,rand)
c
c Returns a uniform random deviate between 0.0 and 1.0. et idum to
c any negative value to initialize or reinitialize the equence.
c This function is taken from W.H. Press'," umerical Recipe" p. 199.
c
cI!Nl/i/f,o0\'#####0\'o\'f,' itNo\'Nil tIt/t/1tNg NN 0\' it,.,. No\'f,'o\'/ttlIi 0\'o\'f,'0\' ,\W/WN1;'1;'{,',o1 o\'f,' f:!#tlo\'J,' fJNItN lIiI#o\'Nh' ##.1 #
c
implicit reaJ*8 (a-h,m,o-z)
save
c implicit real*4(m)
parameter (mbig=4000000.,mseed=16 18033. mz=O.,fac= l.lmbig)
87
c param ter (mbig=lOOOOOOOOO,m ed=161 0 9 ,mz=O fac=l.lrnbi )
c
c According to Knuth, any large mbig, and any mailer (but till large
c mseed can be sub tihlted for the abo e aJue.
c
dimension ma(55)
c
data iff /0/
if (idum.lt.O .or. iff.eq.O) then
iff=1
mj=tuseed-dble(iabs(idum»
mj=dmod(mj.mbig)
ma(55)=mj
mk=l
do 91 i=I,54
ii=mod(21 *i,55)
ma(ii)=mk
mk=mj-mk
if(mk.lt.mz) mk=mk+mbig
mj=ma(ii)
91 continue
do 93 k=I,4
do 92 j=1,55
ma(i)=ma(i)-ma(1 +mod(i+30,55»
if(ma(i).lt.mz) ma(i)=ma(i)+mbig
92 continue
93 continue
inext=O
inextp=31
idum=l
endif
inext=inext+ 1
if(inext.eq.56) inext=1
inextp=inextp+ 1
if(inextp.eq.56) inextp= 1
mj=ma(inext)-ma(inextp)
if(mj.lt.mz) mj=rnj+mbig
ma(inext)=mj
rand=mj*fac
return
end
c liN /i#NN###// // N/I#N#!NJ// NliN /IN NII[f IImltt N#/IN NN NN !J ffh' NN /;' Nh' /iN /IN NfjNNt,' h' /i','NNN//###Nt: N##
88
APPE DIX B: Test package GATST
c#######i? f:I#N !I11 ml;1:/ h'NfjUUNN#h'rIN/;,#,\'11## Nt? #####tt#h' K#/lIIN/ltlttfJ'f;'##################
c
c
c gatst---Test GA packages defined in gapak
c Ting Zhu
c
c####tI ii//h'NNUN f./?f U!J k' #lINNN,;'1/1/#####11#f/#,\'# #/1II'NII'fJ'/tNN Nil' //1I'#fJ'U NN//hWNI!h't.'t/lt/;'Ntil/Nt/fill
c Input variable definitions:
c
c nchrom the number of chromosomes
c fit an array to save fltnes value of every chromosome
c bstidx the best fitted chromosome index
c bstfit the fitness value of the chromosome with best fitness
c wstfit the fitness value of the chromo ome with worst fitness
c avgfit average fitness value of the chromosomes in a generation
c maxgen the maximum number of generations to nm
c ngen the number of generations
c uLimit upper boundary for variable range
c dLimit lower boundary for variable range
c nGray gray coding flag
c 0 disable gray coding
c 1 enable gray coding
c mrate the mutation probability rate
c crate tbe crossover probability rate
c nDbg debug flag
c 0 No debug
c 1 limited debug info
c 2 detailed debug info
c ctype rossover Type
c 0 single point cros over (default)
c I double cros over
c 2 random crossover
c 3 floating point crossover
c nBitSt bit string variable count
c lenStr character length of bit string
c n[nt Integer variable count
c nFloat Floating point variable count
c nStart count of initial variable start point
c nvar Problem specific variable count used by Knapsack or T P
c nUniq chromosome unique flag
c 0 chromosome does not need to be unique
c 1 chromosome must be unique (for example, TSP city must be unique)
c rdflg removing duplicates flag
c 0 no duplicates in chromosome
c 1 duplicates found in chromosome
c nElit number of most fit chromo omes to stay
c xvar external variable 1
c yvar external variable 2
c st tart point array
c###/iN//#/t.i'N .... /I .... #!J1J###lfflfJ################f1###/I#NNN,\'lI'rff.'////h',\'NNN##Ii'II'#N//IIN,'1##
89
c Su routine
c
c input load configuration inf nn ti n
fi tn f each hr 01 ollle c eval evaIuat.e lh
c
cGAP K subroutine :
c
ci2b convert integer to bit- tring
c b2i convert bit-string to integ r
c gray gray code trans ormin!5 on integer
c degray degray code tranSfonnU1~on lJlteg r
c init initialize the first gen ranon of chrom om
c select perform selection for next round
c crover performs crossover
c mutate perfonns mutation
c evalcn evaluates the tilne of all chromo ames
c elit retains the best olution from last g n ration
c func user defined evaluation function u e standard Ro nbro k
c function as a sampl
c csort combsort
c dump shows the debugging infonnation
c shbest prints the best solution
c
c#U##########U##,'l######h'U#U##########U###########n,YN####NUUUUU#UN#######
subroutine input
c
c This subroutine load config infonnation from ga.inp
c
c####tIII f.l1I II!I g#,~#g ggNgggg //#?:fh' N/f,~' Jf f.ff:( lIN tV11#111;'1/###.\'1/#//"liM!tV #/If,'Nil t/!l?IfJlIN //#1111f! ##11
c
implicit real*8 (a-h,o-z)
save
c
parameter (Clmax=80,popmax=30,vamlax=lOIN 1=1, P=6)
c
integer nDbg,nchrom,ctype,n tart maxg n.ind n l1iq 11 lit
integer nBitSt,lenStr,nIntgr,nFloat,uLimit,dLimit,11 ray ntmp
c
double precision bstfit,avgfit wstfit,mrat craie. t val
double precision xvar,yvar,nvar
c
common / gl / st(varmax)
common / g2 / bstfit,wstfit.avgfit,mrat ,crate,val
common / g3 / xvar(ctmax),yvar(ctmax),nvar
common / g6 / nDbg,nchrom,ctype,nStart,maxgen nUniq,nElit
conml0n / gg2/ nBitSt,lenStr nlntgr,nFloat,uLimit,dLimit,nGray
c
c Program ontrol Parameter
c
namelist / ga / nchrom,mrat ,crate,maxgen,nDbg,uLimit,dLimit,
+ ctype,nB itSt,len tr,nlntgr,nGray,nFloat,
+ nStatt I1Var,n niq nElit
c
90
c Load Program ontrol Param t r
c
1 FlLE='ga.inp', T T ='OLD')
READ ( 1 ML = ga)
ntmp=popmax-nchrom
if(nElit.g1.ntmp) then
nElit=ntmp
endif
c
c Load the variable start point
c
READ(IN I ,*) (st(i),i=l,nStart)
CLOSE (INl)
c----------------------------------------------------------c
c Knapsack problem need to load specific iJUO from "Imack.txt"
c
c OPEN(INl, FlLE='knack.txt',STATU ='OLD')
c READ(INI,*) (ind,xvar(i),yvar(i),i=l ,nint(nvar»
c CLOSE (IN1)
c----------------------------------------------------------c
c TSP problem need to load specific info from "city.txt"
c
cOPE (INI, FILE='city.txt',STA S='OLD')
c READ(IN1,*) (ind,xvar(i),yvar(i) i=1 ,nint(nvar»
c CLOSE (INl)
c----------...------------------------- -----.--.------ -----c
c
if(nDbg.gt.O) then
write(LP, *) 'input'
endif
return
end
cli/,' /,' fillit###########################################Nh'N##///1########
subroutine eval(i)
c
c This subroutine evaluates the fitne of each olution
c by calling user defined evaluation function .
c
c Input: i the index of chrom array
c Output: val fitvalue passed back to evalcn
c
ctlllNilNifflUNifll h'#,','NN,',''¥,\'!f!,'f;'Nt;' {,',',',\'t;',\' it tl //,',' #,W111/ If!!!!Nf! Nh' /1#,\','/##### /1# ##N//# Nt//!#
c
implicit real*8 (a-h,o-z)
save
c
parameter (popmax=30,varmax= IO,bitmax= IO,LP=6)
c
integer nDbg,nchrom,ctype,nStart,maxgen,n niq,nElit
integer i,bit t ,ints,jptr,k
C)}
at u imit,dLimit n ra .
c
double pr cision float
double preci ion fit
double preci ion sumfit x I x2 x3, 4 5
double preci ion b tfit,a gfit tfit mrate,crat a1
c
common / g2 / bstfit wstfit a gfit mrate,crate al
common / g6 / nDbg nchrom,ctype,n tart maxgen n lit
common / g9/ jptr(popmax)
conmlon / gg1/ bitSts(popmax,vannax,bitmax ,int (popmax,varrnax)
common / gg2/ nBitSt,lenStr nlntgr,nFloat,uLimit,dLimit n ray
common / gg3/ floats(popmax,vannax) fit(popmax)
c
if(nDbg.gt.l) then
write(LP,*) 'eva!'
endif
c
c Call user-defined function here
c user function has to deal with the bit tring, integer
c floating point and calculate the fitne
c
c--- --------------------------------------------------c
Sample: Rosenbrock Problem
c nBitSt=O; nIntgr= 1; nFloat= 1
c
c
c Convert the floats array to x 1 and x2
c Bit string encoding need to call btoi if necessary
c
xl =t1oats(i, I)
x2=f1oats(i,2)
c
c Call the user_defined subroutine ( tandard)
c
call fLlllc(xl ,x2, val)
c------------------------------------------ _
c
c Sample: Minimization Problem
c nBitSt=O; nlntgr=3; nFloat=2
c
c
c Convert the floats array to x1 and x2
c Bit string encoding need to call btoi if nece ary
c
c xl =ints(i,l)
c x2=int (i,2)
c x3=ints(i,3)
c x4=floats(i, 1)
c x5=floats(i,2)
c
c Call the user_defined subroutine
c
92
c call func(x I ,x2, 3, '4 5, al
c-----------------------------------------------------c
c ample: Bit string sample 0/1 Knap ack problem
c varible is pa d by bit Is array val i returned
c as the total valuable
c
c call fUl1c(i .val)
c-----------------------------------------------------c
c Sample: Restricted sample TSP problem
c variable is non-duplicate integer, val is returned
c as the minimum distance of the route
c
c call fUl1c(i,val)
c-----------------------------------------------------return
end
c
cunu#################U#h'#####,¥,¥#,'l########U#############h'UnUU#N#,'l#U#U#
subroutine func(x 1,x2,val)
c
c This subroutine is the standard Ro enbrock function
c to test combined representation. It evaluates the
c minimizing function
c f(x l,x2)=1 00*(x2-xl **2)**2+(x1-1)**2
c -3<=xl,x2<=3
c
c
c Configuration:
c
c
c
c
c
c
nchrom
nU"ate
crate
maxgen
nDbg
uLimit
10
0.2
0.1
100
1
3
(10 chromo ome p r population)
(mutate rale 20%)
(cro over rate 10%)
(running 6 r 100 generation)
(minimum debug info)
c dLimit -3
c
c
c
c
c
c
c
c
ctype
nBitSt
lenStr
nlntgr
nGray
nFloat
nStart
nUniq
o
o
o
I
o
1
2
o
(not u eel)
(no bit tring encoding
(not LJ ed)
(variable xl)
(not LJ ed)
(variable x.2)
(2 start point xl =-1.2 x2=I .0)
(not used)
c
c//.1/1 tI ######Nt',\' ,I'Nt:,\' ,\'#II,\'Nh'h' //h'#,;'g Ii ,\' t'NtI ti //// r'l,\' II'tI,;'NNtI,vll,\'N#1itI,\',;'NUN,;',\' /tN #,;'tlNt',if,\'//##
c
implicit real*8 (a-h,o-z)
save
c
double precision x I ,x2,val
c
93
val=100.0dO*(x2-xI* 1 * x2- 1*xl + 1-1 *(xl-1)
c write(6,* xl, 2, al
return
end
c
c#####illltt######NNN::h'ttll::Ni1h'It#####N!!II#/iI/Jllt#NI/::""#h'fft/###t:#/fltiNiI/::iifJ/iNNtlf/##
subroutine func2(x 1,x2,val)
c
c This subroutine is the flat-ground Ro enbrock function
c to test combined representation. It evaluates the
c minimizing function
c 11xl ,x2)=100*abs«x2-x1 **2»)+abs(x 1-1)
c -3<=x 1,x2<=3
c
c
c
c
Configuration:
nchrom 10 (10 chromosome per population)
c mrate 0.2 (mutate rate 20%)
c crate 0.1 (crossover rate 10%)
c
c
maxgen
nDbg
100
I
(running for 100 generations)
(minimum debug info)
c uLimit 3
c dLimit -3
c ctype o (not used)
c nBitSt o (no bit string encoding)
c IenStr o (not used)
c nlntgr I (variable xl)
c nGray o (not used)
c nFloat 1 (variable x2)
c nStart 2 (2 tart point xl =-1.2 x2= 1.0)
c nUniq o (not u ed)
c
c################/ih'h'/iIl/i##############ilt/iiiillilNtllI!llll/#########/i/,'t/###########
c
implicit real*8 (a-h,o-z)
save
c
double precision xl ,x2,val
c
vaI=100.0dO*abs(x2-xl **2)+abs(xl-1)
return
end
c
c##########Nh't/#h'/f!!!I#####N/iJ/###tlNNN::N/ih'lli/lti/##t\'I/NiI########tI#/tIth'lItJlI/iNh',.,./f
subroutine func3(x I ,x2,val)
c
c This subroutine is the hollow-ground Rosenbrock function
c to test combined representation. It evaluate the
c minimizing function
c f(x.1,x2)=100*sqrt(abs«x2-xl **2»)+ qrt(abs(xl-l»
c -3<=xl,x2<=3
c
c
94ı
c
c
onfigurati
I1chrom
11:
LO 10 cm 1110 m p r p pulaljon
c l11Tate 0.2 (mulat rat 20%
c
c
c
maxgen
nDbg
crate 0.1
LOa
1
(r 0 rrat 10%)
(running fi r 100 g n rati
(minimum debug info)
n
c uLimit 3
c dLimit -3
c ctype o (not u ed)
c nBitSt o (no bit tring encoding
c lenStr o (not u ed)
c nIntgr 1 (variable xl)
c nGray o (not used)
c nFloat I (variable x2)
c nStart 2 (2 start point xl=-1.2 x2=1.0)
c nUniq o (not used)
c
c################Nh'h'NKh'Nt/NNN#.... tJ####Ith'Nh'#NIi#Nh'NtlIN;#h'h'##N#j~:/h'NNNh'##//#I///NtI#
c
implicit real*8 (a-h,o-z)
save
c
double precision xl ,x2,val
c
val=1 OO.OdO*sqrt(abs(x2-x I **2»+ qrt(abs(x 1-1»
retum
end
c
c#####N ,YI///NUll,;'/;' // /I ;;#######/1//N,;'// #####/11/#NN#NNNNltUA' Nh'# N,~/I #{IN A' /IN/lIf##It/th' INt
subroutin func4(x1,x2,x3,x4 x5,val
c
c This subroutine i. function to te t combined r pr entation.
c It evaluates the minimizing function
c f(x 1,x2,x3,x4,x5)=x I*x 1+x2*x2+x3 *x3+x4*x4+x ·x5
c
c Configuration:
c nchrom 10 (10 chromosome per population)
c l11Tate 0.2 (mulate rate 20%)
c crate 0.1 (ro over rate 10%) .
c maxgen 100 (running for 100 gen ration)
c nDbg 1 (minimum debug infi )
c uLimit 3
c dLimit -3
c ctype o (not u ed)
c nBitSt o (no bit string encoding)
c lenStr o (not u ed)
c nlntgr 3 (variable xl,x2,x3)
c nGray o (not used)
c nFloat 2 ( ariable x4,x5)
c nStart o (no sta.rt point)
e n niq o (not 1I ed)
c
eNtiN NJ,'######ff#//#N//NI? Nt;'Nh'N h'N!/##########!!NNNII (J NN/I/!!ftlll//h'#tlh'tfl/llh'h'#Jf/lh' Nt/N N/1h'1t
95ı
c
implicit real*8 (a-h,o-z
save
c
double precision xl 2 x3,x4 x5 al
c
val=x 1*xl +x2*x2+x3*x3+x4*x4+x5* 5
return
end
eN //1/NN##N#N ///fNf:lh' UNNh'f/I/N// UNH,;'// Nfl' ,Y// .;'1/#,;'// NNflA'N#////##/1 A' NI/NtI,;' #//####///11///#NN#
subroutine func5(ichrom,val)
c
c This subroutine is to test bit string repre entation.
c The 0/1 Knapsack problem has the following external setting
c
c Input:
c iehrom: index ofchromosome
c Output:
c val: valuation
c
c item weight price
c 1 100 40
e 2 50 35
c 3 45 18
e 4 20 4
c 5 10 10
e 6 5 2
e
e Configuration:
e nchrom 10 (10 chromo ome per population
e mrate 0.2 mutate rate 20%)
c crate 0.1 (ero saver rate 10%)
e maxgen 100 (nlOoing for 100 gen ration )
c nDbg 1 (minimum debug info)
c uLimit a
c dLin'llt o
e etype 1 (single-cro sover)
c nBitSt 1 (one variable)
e lenStr 6 (total 6 items)
e nIntgr a (not u ed)
e nGray o (not u ed)
e nFloat a (not u d)
c nStart o (no start point
c nvar 6 (total 6 item)
c n niq o (not used)
c
cNNh' /J N#//N// //fiNNNN .1//UtiA' //,;'#N////.;'##11#//tIll fill' N,;'##11#////NN UNgj~f/h't1 #N#NN gN,;' NA'ttN NgNA'I/#
c
implicit reaJ*8 (a-h,o-z)
save
c
parameter (ctmax=80,popmax=30,vannax=1O,bitmax=IO,LP=6)
c
96ı
int ger bitSts,ints,i,ichrol11
c
double precision cap,wt, al x ar,yvar n ar urn
c
common / g3 / xvar(ctmax),yvar(ctmax nvar
common / ggl/ bitSts(popmax,vannax bitmax) int popmax varmax)
c
c
c Calculate capacity
c
cap=O.OdO
sum=O.OdO
do 62 i=1,nint(nvar)
cap=cap+xvar(i)
sum=sum+yvar(i)
62 continue
cap=capl2.0dO
c
c Sum the weights and profits
c
wt=O.OdO
val=O.OdO
do 63 i=l,nint(nvar)
wt=wt+bitSts(ichrom,1,i)*xvar(i)
val=vaJ+bitSts(ichrom,l,i)*yvar(i)
63 continue
c
c Over capacity, drop this solution, set the fit to minimum
c
if(wt>cap) then
val=sum
else
c
c Record the profits, the better value the les val to fi l
c the minimization algorithm of other samples
c
val=sum-val
endif
return
end
ctJIINh'NII##########tJilfltJ#h'#####IIt1h'Nh'#h'Nfllill###N,','I/Nm:,','h'h'##ltttN,','N//NNtIt!N###N##1/
subroutine func6(ichrom val)
c
c This subroutine is to test re tricted integer representation.
c The TSP problem has the following external setting
c
c Input:
c i.chrom: index of chromosome
c Output:
c val: valuation
c
c city x-location y-locatiol1
cIS 5
97ı
c
c 2 -6
3 3
c 4 1
c 5 6
c 6 -I
c 7 0
c 8 4
c 9 -4
c
c Configuration:
c nchrom
c mrate
c crate
c maxgen
c nDbg
c uLimit
c dLimit
c ctype
c nBitSt
c lenStr
c nlntgr
c nGray
c nFloat
c nStart
c nvar
c nUniq
c
c
10
0.1
0.1
100
2
9
I
0
0
0
9
0
0
0
9
I
-8ı
3ı
7ı
2ı
4ı
-5ı
5ı
-3ı
(10 chromosome per population)ı
(mutate rate 20%)ı
(crossover rate 10%)ı
(running for 100 generation)ı
(minimum debug info)ı
(single-crossover)ı
(not used)ı
(not used)ı
(for each city)ı
(not used)ı
(variable x4,x5)ı
(no start point)ı
(total 9 cities)ı
(each city must appear only once)ı
implicit real *8 (a-h,o-z)
save
parameter (ctmax=80,popmax=30,vannax=1O,bitmax= 1O,LP=6)
c
integer bitSts,ints,i,ichromJ,k,rdflg
integer nDbg,nchrom,ctype,nStart,maxgen n niq,nElit
integer nBitSt,lenStr,nIntgr,nFloat,uLimit,dLin:tit,nGray
c
double precision val,xvar,yvar,nvar,v I,v2
c
common! g3 I xvar(ctmax),yvar(ctmax),nvar
common! g6! nDbg,nchrom,ctype,nStart,maxgen,nUniq,nElit
common! ggl! bitSts(popmax,varmax,bitmax),ints(popmax,varmax)
common! gg2! nBitSt,lenStr,nlntgr,nFloat,uLimit,dLimit,nGray
c
c Check whether the chromosome is unique
c
rdflg=O
if(nUniq.eq.l.and.nJntgr.gt.l) then
do 64 i=1,nIntgrı
do 65 j=i+I ,nlntgrı
if(ints(ichrom,j).eq.ints(ichrom,i» thenı
rdflg=lı
endifı
98
65 continue
64 continue
endif
c
c Duplicate chromo orne as ign th \ or t alue
c
if(rdllg.eq.l) thenı
al=999999.0dOı
else
c
c Calculate the route
c
val=O.OdO
do 66 i=l,nlntgr-lı
vI =(xvar(ints(ichrom,i»-xvar(ints(ichrom,i+1»)**2ı
v2=(yvar(ints(ichrom i»-yvar(ints ichrorn,i+1»)**2ı
val=val+sqrt(vl +v2)ı
66 continue
vi =xvar(ints(ichrorn,1»**2+yvar(ints(ichrom, 1»**2
v2=xvar(ints(ichrorn,nlntgr»**2+yvar(ints(ichrom,nlotgr )**2
val=val+sqrt(v 1)+sqrt(v2)
endifı
endı
eNaNl/fr'n!ll/llNNI//I//t! #NIINlI//Nh'N //#//// /IN NtfNfltI#U//NNNN#tll/#Nh'//N## #//fI,vA' gNO/;, /I N##
99ı
ITA
Ting Zhu
andidate for the Degre of
Master of cience
Thesis: AGE ERAL G NETI ALGORIT PA KA
Major Field: omputer Science
Biographical:
Personal Data: Born in Shanghai, China, Apri I 21, 197), the daught r Helin Zhu and Mrs. Qiuzhen Zhu.
Education: Received Bachelor of Engineering degre in h mical Engin ring
from Beijing Polytechnic University, hina, in July 19 9. ompleted requirements for Master of cience degree in omputer cience at the
Computer Science Department at Oklahoma State niversity in ecernber
2003.