下载 > 资源分类 >  开发技术 >  C > 王小平版遗传算法的光盘源代码

王小平版遗传算法的光盘源代码

2004-06-25 上传大小:3.79MB
王小平版遗传算法的光盘源代码
		SGPC: Simple Genetic Programming in C
		by Walter Alden Tackett and Aviram Carmi
			(gpc@ipld01.hac.com)
Version 1.1
(c) 1993 by Walter Alden Tackett and Aviram Carmi
This code 
and documentation is copyrighted and is not in the public
domain.  All rights reserved.
Genetic Programming is a method of "Adaptive Automatic Program
Induction" originally created by John Koza and James Rice of Stanford
University.  SGPC is a C implementation of Genetic Programming: it is
a C program which writes LISP programs.  These programs are tailored
by the system to solve a problem specified by the user.  Koza and Rice
have provided to the public a version of Genetic Programming which is
written in LISP.  SGPC offers greater portability and about 25-50
times improvement in execution speed due to a highly optimized C
implementation.
For further information on Genetic Programming See: 
_Genetic_Programming_ by John R. Koza, MIT Press 1992
"Genetic Programming for Feature Discovery and Image Discrimination"
by Walter Alden Tackett in _Genetic_Algorithms:_Proceedings_of_the_
Fifth_International_Conference_ (GA93), S. Forrest Ed., Morgan-
Kaufman 1993
To participate in our on-line Internet e-mail forum send your
subscription request to:
genetic-programming-request@cs.stanford.edu
Basically, the code does the same things that Koza & Rice s simple
LISP does and is set up to handle multiple populations as well (e.g.,
for co-evolution).  You need to provide three modules, setup.c,
fitness.c, and prob.h, in a subdirectory named PROBNAME, where
PROBNAME is some descriptive name of the problem.  E.G., in the
version we ship we include REGRESSION/setup.c and
REGRESSION/fitness.c, Which do Koza s simple regression problem.
setup.c contains functions to setup the function table, the terminals
table, and code for the functions in the function table.  prob.h
contains prototypes for the user defined functions.  fitness.c
contains functions to evaluate and validate populations and trees,
early termination, and definition of the fitness (training and test)
cases.
As a second example, for your enlightenment, we include the ADF
problem which shows you how to build a simple 2-class "dendritic"
classifier (see my paper in the sfi account).
You should not need to modify any of the other myriad files.
COMPILING
Source code for the kernel system is in the sub-directory `lib .
Source code for problem depended modules are in sub-directories named
after the problem.
There is a Makefile in the top level directory which invokes the
Makefile in the problem specific directory, which invokes the Makefile
in the `lib  directory (if needed).  The source in the lib directory
is compiled into an object library file, which is then linked with the
problem specific objects.
Read the notes in the Makefiles in all the sub-directories, make any
necessary changes to fit your system, and then type:
make depend PROBLEM=PROBNAME
make PROBLEM=PROBNAME
where PROBNAME is the name of the subdirectory where the problem
specific setup.c and fitness.c files are.
EXECUTING
the executable is called gpcPROBNAME and will be in
the PROBNAME directory.
gpcPROBNAME  [-d nrow ncol] npops ngen (pop0_pfile|`none )... [seed]
NOTE: you must have a parameters file name for each population.
EXAMPLE
gpcREGRESSION 2 100 none pop1_file 1234
will run gpcREGRESSION with 2 pops 100 gens with pop0 using the
default values, pop1 using values from pop1_file, and 12345 as the
initial random seed.


On startup default values for the runtime parameters are assigned from
hard-coded values, then if a file called "default.in" exists in the
current directory, values are read from it and override the hard-coded
values.  If a parameters file name for a population is present on the
command line, values from this file override the previous values for 
that population, else if `none  is specified on the command line, the
parameters will retain the default values.  Remember you must specify
either a population params file or `none  on the command line for
each population.

Note: since the random seed value is not a population parameter but it
can be specified in the population parameters file, if there are
multiple populations, and no seed value was specified on the command
line, the value read from the last population parameters file will be
used.


Some salient points about the modules which are provided for you:

The main() is located in lib/gpc.c 

The top-level loop which iterates over the generations is in generations.c 
The data structures which you must work with are in the file gpc.h 
Expressions (trees) are evaluated via calls to eval(tree *t) in eval.c.
Trees are operated on using routines in treeops.c and can be read/written
using operations in treeio.c.

You will get some tutorial feel for using the data structures involved
by examining the initializations which take place in populations.c and
generations.c.

In general, the modules are descriptively named: e.g., selection.c,
crossover.c, mutation.c.


CREATING YOUR OWN PROBLEMS

First create a sub-directory under the top-level sgpc directory and
name it a descriptive name. Copy the Makefile and optionally the 
fitness.c setup.c and prob.h files to the new directory.  


FITNESS.C

Here are the functions you must include in the fitness.c module:

/* 
 assigns standardized fitness  values to all members of each population 
 pop[0]...pop[numpops-1]
*/
void evaluate_fitness_of_populations ( 
  int numpops, 		/* number of populations */
  int numgens, 		/* number of generations */
  pop_struct *pop 	/* the population array */
  );


/* 
 returning != 0 from this routine halts SGPC at the end of the generation, 
 eg, if a "perfect" (ha!) individual is found
*/
int terminate_early ( 
  int numpops,
  int numgens,
  pop_struct *pop
  );


/* 
 creates the array of fitness cases, or does other startup peculiar 
 to your problem 
*/
void define_fitness_cases ( 
  int numpops,
  int numgens,
  pop_struct *pop
  );


/* 
this routine is used to test the best-of-generation individual against
a separate set of test cases which were not used in training (i.e., in
generating the fitness values which drive selection).  The best-of-run
individual is determined using the figure returned from this function
*/
float validate_fitness_of_tree( 
     int	numpops,
     int	numgens,
     pop_struct *pop,
     tree 	*t
     )


SETUP.C

Here are the functions you must include in the setup.c module:

/* 
 assigns function pointers, print names, arity, macro-flag, etc, to 
 function table entries for all populations 
*/
void make_function_table ( 
  pop_struct *pop
  );


/* 
 assigns function pointers, print names, arity, macro-flag, etc, 
 to terminal table entries for all populations 
*/
void make_terminal_table ( 
  pop_struct *pop
  );

In addition, you declare all of the actual function code for you
function set in setup.c.  A declared function can either be a
function or a macro: a function has an array of values (eg float
*args;) passed into it as arguments, whereas a macro has an array of
unevaluated expressions passed in, so that some of them may remain
unevaluated to prevent side-effects.

Here is how the properties of a function are assigned in
make_function_table(pop_struct *pop):

  pop[0].function_table[0].arity = 2;
  pop[0].function_table[0].macro = FALSE;
  pop[0].function_table[0].enabled = TRUE;
  pop[0].function_table[0].printname = "+";
  pop[0].function_table[0].code = plus;

Here is the assignment of a macro:

  pop[0].function_table[4].arity = 4;
  pop[0].function_table[4].macro = TRUE;
  pop[0].function_table[4].enabled = TRUE;
  pop[0].function_table[4].printname = "IFLTE";
  pop[0].function_table[4].code = iflte;

Here is how the functions they point to are declared:

For the function plus:

GENERIC plus(GENERIC *args)
{
  return args[0]+args[1];
}

For the macro iflte:

/* note that args are unevaluated trees, not GENERIC values */
GENERIC iflte(tree **args)
{
  return ((eval(args[0]) < eval(args[1])) ? eval(args[2]) : eval(args[3]));
}

Note that in the code above, the type generic can be set by the TYPE
definition set to the make file: default is #define GENERIC float.


TERMINAL TABLE:
We play some games here.  Here is the definition of a terminal from
make_terminal_set(pop_struct *pop):

  pop[0].terminal_table[0].val = 0;
  pop[0].terminal_table[0].printname = "X";
  pop[0].terminal_table[0].constant_generator = random_constant;

If we declare that there are N terminals in the terminal set, then there
a total of N+1 entries 0...N, where entry N is the randomly generated
constant, which should always be declared as follows:

  pop[0].terminal_table[pop[0].terminal_table_size].val = 0;
  pop[0].terminal_table[pop[0].terminal_table_size].printname = FORMAT;
  pop[0].terminal_table[pop[0].terminal_table_size].constant_generator =
    random_constant;

Here, FORMAT is #defined to be the format string associated with the 
GENERIC type, eg if GENERIC == float then FORMAT == "%f".


SAMPLE POPULATION PARAMETERS FILE:

seed = 11287			# use this if no value for seed on command line
population_size = 100		
max_depth_for_new_trees = 6   
max_depth_after_crossover = 17
max_mutant_depth = 4
grow_method = RAMPED		# FULL GROW
selection_method = FITNESSPROP	# TOURNAMENT
tournament_K = 6		# used only if TOURNAMENT is selected
crossover_func_pt_fraction = 0.2
crossover_any_pt_fraction = 0.2
fitness_prop_repro_fraction = 0.1
parsimony_factor = 0.00000


CHECKPOINTING:

To enable checkpointing, a non zero value for checkpoint_frequency 
must be specified in the default parameters file, e.g.,

checkpoint_frequency = 10

Remember that if you specify value in the population s parameters
file, the value read from the last parameters file will be used as the
checkpoint frequency for all the populations.

The generated ckptfile is named gpc_`hostid _`pid .ckpt.Z, 
i.e. it is compressed using the compression utility specified in the 
makefile

(Note: ignore ckpt files that are not compressed, the process could
have crashed while writing the uncompressed file and it is probably
corrupted.  Of course, this is assuming that you have `compress  on
your system.)

To recover from a crash, just uncompress the ckpt file and type in:

gpc -r ckpt_file_name

As a bonus you can now extend a run for more generations (only if
checkpointing is enabled, i.e. checkpoint_frequency is greater than
zero. Set it to a large value if you do not want checkpointing to slow
you down, but do want a checkpoint file for the last generation).  To
do this, just edit the ckpt file and change the value ONLY for the
following line (it should be the fourth line in the file):

number_of_generations = 100
                        ^^^
to the new total number of generations, i.e. to extend the run by 10 gens
replace 100 by 110.

****************************************************************************
FAQ S FROM OUR EMAIL ARCHIVES:

> First, do you use mutation?  I couldnt find a  mutation  parameter
that easily accessible...

Yes.  It is implicit, like in Koza & Rice s code: it is
1.0 - (crossover_func_pt_fraction + crossover_any_pt_fraction + 
       fitness_prop_repro_fraction)

> 
> Second, do you have a facilty for inserting pre-created individuals into the
> population?

Yes- the load_from_file keyword in the parameter file, e.g.:

load_from_file = foo.lsp

...in your input parameter file will load the N lisp expressions in
file foo.lsp as the first N elements of the population.
Also, *don t* include the load_from_file keyword unless you are actually
loading a file.

> Thanks for the info...I was also curious how I could prohibit the 
> random constants from being terminals...ie I do not wish/need to use 
> random constants and I was wondering how best to remove them...The solution 
> is somewhat obvious maybe (dont include them in the terminal table) but then
> I was a bit concerned given all of the warnings that there are N+1
> terminals..

> 

Yet another undocumented feature (YAUF :), in lib/gpc.h change:

#define ALLOW_CONST 1

to:

#define ALLOW_CONST 0

You will need to recompile the entire libgpc object library.  i.e.,
you cannot have this set to different values for different problems
w/o recompiling the whole damn thing.



SGPC 1.0 is shipped with three makefiles:

Makefile - sun-specific makefile: slick, cryptic, non-portable.

gMakefile - gnu makefile: you can find gnu make for most machines.  Ask
	your local systems hacker to help you find it on the net and
	install it.

make.script - a shell script for compiling SGPC, may require some editing
	if you have changed directory names or the PROBLEM you are working
	on.  Basically, if you can t run this you re not running Unix.

The c-code itself should be portable to standard Unix systems.  The only
portability issues should surround the use of the system qsort routine (we
provide one ourselves, anyway) the timing routines (you don t need this
unless you re anal, anyway) and mallopt (you don t *have* to use mallopt,
but it helps to ensure locality and reduce fragmentation).  Of course this
is only an estimate and your actual mileage may vary.
...展开收缩
综合评分:4.1(131位用户评分)
直接下载 开通VIP会员 免积分下载

评论共有11条

name
animenut2013-09-02 18:47:18
课程学习时参考用,实际使用时需改代码,代码通用性还是有欠缺
name
noshy2013-05-26 07:52:39
配合原书会更有学习的价值。
name
kkao1262013-03-21 17:49:36
有参考价值,比较经典
name
bingxingarm2013-03-19 08:53:19
程序是有点儿老 用起来不是太舒服 不过可以参考
name
yudianer9182013-03-05 15:57:47
程序用C编的,具有一定可借鉴性,参考编写修改
name
xgwdy062013-01-08 10:37:15
很具有参考价值,但确实有点老
name
chenqy9992012-10-29 21:14:08
程序太老了,但是参考价值
name
sichuanyinjunyu2012-09-15 22:09:12
算法程序设计这一块应该是另外一个老师出的,挺好,赞一个!!!
name
sherlys2012-08-05 21:11:10
是挺好的,不过是挺老的
name
insaneguy2012-06-04 22:25:20
学习遗传算法必备,王小平的书是很有参考价值的

评论资源

您不能发表评论,可能是以下原因:

登录后才能评论

待评论资源
 

热门专辑

关闭
img

spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip

CSDN VIP年卡 4000万程序员的必选现在开通,立省522元
下载
img

王小平版遗传算法的光盘源代码

会员到期时间:剩余下载个数:
VIP下载

积分不足!

资源所需积分 当前拥有积分
您可以选择
开通VIP年卡
4000万
程序员的必选
600万
绿色安全资源
现在开通
立省522元
或者
购买C币兑换积分 C币抽奖
img
资源所需积分 当前拥有积分
VIP年卡全年1200个资源免积分下载促销价78元,开通立省522元
下载
下载

兑换成功

你当前的下载分为234开始下载资源
你还不是VIP会员
开通VIP会员权限,免积分下载
立即开通

你下载资源过于频繁,请输入验证码

你下载资源过于频繁,请输入验证码

您因违反CSDN下载频道规则而被锁定帐户,如有疑问,请联络:webmaster@csdn.net!

举报

若举报审核通过,可奖励20下载分

  • 举报人:
  • 被举报人:
  • 举报的资源分:
  • *类型:
  • *详细原因: