Algorithm 版 (精华区)

发信人: shs (花雨飘), 信区: Algorithm
标  题: 遗传算法（1）
发信站: 哈工大紫丁香 (Sat Sep  9 12:58:56 2000), 转信

先前答应了人家，现在兑现，呵呵。
这一篇是说明。
                             COPYRIGHT NOTICE
This software is copyright by Zbigniew Michalewicz. Permission is
granted to copy and use the software for scientific, noncommercial
purposes only. The software is provided "as is", i.e., without any
warranties.
                              GENERAL REMARKS
The Genocop system aims at finding a global optimum (minimum or
maximum: this is one of the input parameters) of a function;
additional linear constraints (equations and inequalities) can
be specified as well.
This is a first version of Genocop system (version 1.0); it is meant to be
a pre-release only. This version was implemented by one of my master
students, Swarnalatha Swaminathan.
Next versions would aim at better user interfaces
and at improving usability of the system (different termination conditions,
declaring integer and boolean variables, etc.). In summer 1993 I plan also
to release Genocop II, which would handle nonlinear constraints as well.
The system is based on the article "GENOCOP: A Genetic Algorithm for
Numerical Optimization with Linear Constraints" accepted for publication
in the Communications of the ACM. The paper was accepted there in
April 1991 (16 months ago) and until today the editors of CACM did not
schedule it in the coming issues of the journal. However, the article
was incorporated (with a permission from the ACM) into one of the chapters
of my new book "Genetic Algorithms + Data Structures = Evolution Programs"
(Springer Verlag, August 1992).
The current version of Genocop should run without changes on any BSD-UN*X
system (preferably on a Sun SPARC machine). Note, however, that the
system was NOT designed with portability in mind, i.e., the partability
was not the main factor in the design process.
                        HOW TO RUN THE GENOCOP SYSTEM
To run the genocop system, there are four simple steps to follow:
(1) prepare input file, say, "your_input",
(2) incorporate the function in the eval.c file,
(3) type "make",
(4) type "genocop your_input your_output" ("your_output" is the name
    of the output file provided by you).
A simple example follows. The input file of this example is the
transferred file "input" you have now in your directory, the typical
output is present in the file "output". The function is already
incorporated in the file "eval.c".
In the example we try to maximize a function of 4 variables:
  X[1]*sin(X[2]) + X[3]*X[3] -12.7*X[4]
(NOTE: indexes of variables start from one, and not zero).
Additional requirements are:
one linear equality:
    2*X[1] + X[2] - 3.5*X[4]  =  1
two linear inequalities:
    X[2] + X[3]   <=  3.00
    X[1] - 2*X[2] <=  0.00
Also:
 1.00   <=  X1   <=    8.00
 0.00   <=  X2   <=    8.00
-2.10   <=  X3   <=    3.10
 0.00   <=  X4   <=    4.40
The input file "input" is as follows (see file "input"):
___________________________________________________
4 1  2 4
2.0     1.0     0.0     -3.5     1.0
0.0     1.0     1.0      0.0     3.0
1.0    -2.0     0.0      0.0     0.0
1.0 1 8.0
0.0 2 8.0
-2.1 3 3.1
0.0 4 4.4
70 500
4 4 4 4 4 8
0.2
1
2
0.25
10
___________________________________________________
Explanations (line by line) of the input file:
4 1  2 4
These four integers have the following meaning (in order):
number of variables,
number of equalities,
number of inequalities,
number of domains specified.
The next line:
2.0     1.0     0.0     -3.5     1.0
represents the equation:
 2*X[1] + X[2] - 3.5*X[4]  =  1;
note, that for 4 variables you must provide 5 numbers (one for each variable
and the additional one for a value of the right hand side of the equation).
The next two lines:
0.0     1.0     1.0      0.0     3.0
1.0    -2.0     0.0      0.0     0.0
represent two inequalities. NOTE, that all inequalities assume that
left hand side is LESS OR EQUAL to the right hand side. In other words,
to represent an inequality:
       3.1*X[2] - 4.9*X[4] >= 12.1
you have to represent it as (assuming four variables):
      0.0    -3.1     0.0     4.9    -12.1, i.e.,
      -3.1*X[2] + 4.9*X[4] <= -12.1
The next four lines of the input file:
1.0 1 8.0
0.0 2 8.0
-2.1 3 3.1
0.0 4 4.4
describe domains of variables (the middle - integer - number of
each line serves as an index of a variable).
The line:
70   500
indicate the population size (70) and the total number of generations (500).
The next line:
4 4 4 4 4 8
provides the frequencies of 6 operators (these are integers; their total
should not exceed 50% of the population size).
You can leave these frequencies as a standard set for all your
experiments.
The final lines of the input file are:
0.2    (the coeficient q for cumulative probability distribution;
        higher q values provide stronger selective pressure;
        standard value 0.2 is already relatively high for a population
        size 70).
1      (1 is for maximization problem, 0 for minimization).
2      (a parameter for non-uniform mutation; should stay as 2).
0.25   (a parameter for arithmetical crossover, float between 0 and 1).
10     (a parameter for simple crossover, leave it as it is).
EVALUATION FUNCTION:
One of the transferred files is "eval.c". For our current example,
it is:
_____________________________________________________
#include "thesis.h"
float evaluate(X)
VECTOR X;
{
 return(X[1]*sin(X[2]) + X[3]*X[3] -12.7*X[4]);
}
_____________________________________________________
To provide any function, just replace return line with
appropriate expression, note again that variables are:
X[1], X[2], etc.
If you change the function, you will have to retype "make".
Now, everything is ready. Just type:
% make
and
% genocop your_input your_ouput
and (hopefully) you'll get your result.
IMPORTANT REMARKS:
(1) If the input file contains more than one equations, these equations
    must be linearly independent (this is responsibility of the user).
(2) There is a line in the thesis.h file:
#define TRIES 100
The variable TRIES defined the number of attempts the Genocop system
tries to find a feasible point in the search space. If successful,
the system will run further. If not, the Genocop will prompt you
for an initial point.
OUTPUT: the output file is self-explanatory. After several control
lines, you get the generation number and the current best value
(for generations, where there is an improvement).
This is followed by the final population.
FINAL NOTICE: It is quite likely that there are some bugs in the system;
              please, report them to zbyszek@mosaic.uncc.edu.
              I will try to take care of them in the next version (1.1).
I hope these remarks would be sufficient to experiment with the system.
Happy optimizing,
Zbigniew Michalewicz
******************************************************************************
* Mail: Department of Computer Science      E-mail: zbyszek@mosaic.uncc.edu  *
*       University of North Carolina        Phone:  (704) 547-4873           *
*       Charlotte, NC 28223                 Fax:    (704) 547-2352           *
******************************************************************************



--
○/ Ｖ／＼Ｖ \
\ㄨ/<○> ┃
○＜＞<┃><//>
((<\\>  ))
＼○／ ┃／\
脖子扭扭，屁股扭扭，大家一起来跳舞

※ 修改:．shs 于 Sep  9 12:56:27 修改本文．[FROM: as.hit.edu.cn]
※ 来源:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: 211.69.196.11]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: as.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: shs.bbs@bbs.whnet.ed]