📄 gaa.html
字号:
<html>
<head>
<title>The GA Playground: The Genetic Algorithm Toolkit</title>
<META HTTP-EQUIV="keywords" CONTENT="Java,Genetic Algorithm,Interactive Experiment,Toolkit,GA,TSP,Knapsack,BinPacking, Multi-modal, Optimization, Ackley, Rosenbrock, Schwefel, Rastrigin, Griewank, SphereModel, Evolutionary Algorithm,Applet,Application,Free Download">
<META HTTP-EQUIV="description" CONTENT="The GA Playground is a general purpose GA toolkit implemented in Java, designed for experimenting with genetic algorithms and handling optimization problems of diverse kinds.">
<META HTTP-EQUIV="author" CONTENT="aridolan@netvision.net.il">
</head>
<BODY BGCOLOR=#FFFFFF>
<Center><IMG SRC="gaatitle.jpg" WIDTH=500 HEIGHT=50 ALT="The GA Playground"></Center>
<p>
<Center><H4>A general GA toolkit implemented in Java, for experimenting with genetic algorithms and handling optimization problems</H4></Center>
<br>
<p>
<U><Center><H3>Contents</H3></Center></U>
<A NAME="GAA"></A><A HREF="#GAA"><B>The GAA Applet/Application</B></A>
<UL>
<LI><A HREF="#Overview">Overview</A>
<LI><A HREF="#Requirements">Browser Requirements and Loading Times</A>
<LI><A HREF="#General Notes">General Notes</A>
<UL>
<LI><A HREF="#Alphabet">Alphabet</A>
<LI><A HREF="#Definition Files">Problem Definition - Definition Files</A>
<LI>
<A HREF="#Source Modifications">Problem Definition - Source Modifications</A>
<LI><A HREF="#Special Mechanisms">Special GA Mechanisms</A>
<UL>
<LI><A HREF="#Kick">Automatic 'Kick'</A>
<LI><A HREF="#Kin Competition">Kin-competition compensating factor</A>
<LI><A HREF="#Memory">Memory</A>
<LI><A HREF="#Extra Functions">Pre & Post Breed Functions</A>
</UL>
<LI><A HREF="#UDF">Interactively (on-the-fly) defined functions</A>
<LI><A HREF="#Continuous Reporting">Continuous Reporting</A>
<LI><A HREF="#Graphic Display">Graphic Display</A>
<LI><A HREF="#File IO">File Input/Output</A>
<UL>
<LI><A HREF="#Application IO">Application Mode IO</A>
<LI><A HREF="#Applet IO">Applet Mode IO</A>
</UL>
<LI><A HREF="#Online Help">Online Help</A>
</UL>
<LI><A HREF="#Download">Download and Installation</A>
<UL>
<LI><A HREF="#Applet">Applet Mode</A>
<LI><A HREF="#Application">Application Mode</A>
<LI><A HREF="#Classpath">Classpath (Application mode)</A>
<LI><A HREF="#Batch">Application Batch File</A>
</UL>
<LI><A HREF="#Feedback">Limitations and Request for feedback</A>
</UL>
<p>
<A HREF="#Examples"><B>Examples and Test Problems</B></A>
<UL>
<LI><A HREF="#Examples General">General</A>
<LI><A HREF="#Examples Notes">Important Notes</A>
<LI><A HREF="#Demo Problems">List of demo problems</A>
<UL>
<LI><A HREF="#Multiple Problems">Multiple Problems Applets</A>
<UL>
<LI><A HREF="#Demo All">All demo problems</A>
</UL>
<LI><A HREF="#Demo Tsp">TSP</A>
<UL>
<LI><A HREF="#TspDemo">TspDemo - All cities on a circle</A>
<LI><A HREF="#TspBayg29">TspBayg29 - 29 cities in Bavaria</A>
<LI><A HREF="#TspAtt48">TspAtt48 - 48 capitals of the US</A>
</UL>
<LI><A HREF="#Demo Knapsack">Knapsack Problems</A>
<UL>
<LI><A HREF="#Knapsack01">A single knapsack problem</A>
<LI><A HREF="#KnapsackWeing1">A Multiple knapsack problem (Weing1)</A>
<LI><A HREF="#KnapsaclWeish01">A Multiple knapsack problem (Weish01)</A>
</UL>
<LI><A HREF="#Demo BP">Bin Packing Problems</A>
<UL>
<LI><A HREF="#Binpack1_00">Binpack1 u120_00 (120 Objects)</A>
<LI><A HREF="#Binpack5_19">Binpack5 t60_19 (60 Objects in triplets)</A>
</UL>
<LI><A HREF="#Demo FA">Facility Allocation</A>
<UL>
<LI><A HREF="#Steiner">Steiner - All cities on a circle</A>
<LI>
<A HREF="#SteinerByFile">Steiner - Cities coordinates read from a file</A>
</UL>
<LI><A HREF="#Demo Multi-modal">Multi-Modal Functions</A>
<UL>
<LI><A HREF="#Ackley">Ackley's function</A>
<LI><A HREF="#Rosenbrock">Rosenbrock's function</A>
<LI><A HREF="#Schwefel">Schwefel's function</A>
<LI><A HREF="#Rastrigin">Rastrigin's function</A>
<LI><A HREF="#Griewank">Griewank's function</A>
</UL>
<LI><A HREF="#Demo Functions">Simple Function Optimization</A>
<UL>
<LI><A HREF="#SphereModel">SphereModel</A>
<LI><A HREF="#SingleVarMin">Single Variable Minimization</A>
<LI><A HREF="#MultiVarMin">Multiple Variable Minimization</A>
<LI><A HREF="#Simpleton">Simpleton - A trivial 10 variables problem</A>
</UL>
</UL>
</UL>
<br>
<p>
<A NAME="Overview"></A><Center><U><H3>Overview</H3></U></Center>
<p>
The GA Playground is a general purpose genetic algorithm toolkit where the user can define and run his own optimization problems. The toolkit is implemented in the Java language, and requires (when used as an application, in its full mode), a Java compiler and a very basic programming knowledge (just enough for coding a fitness function). Defining a problem consists of creating an Ascii definition file in a format similar to Windows Ini files, and modifying the fitness function in the GaaFunction source file. In addition, other methods can (optionally) be overwritten (e.g. the drawing method), other classes can be extended or replaced, and additional input can be supplied through Ascii files.
<p>
The GA Playground is primarily designed to be used as an application and not as an applet, since it requires re-compiling of at least one class and use of local file I/O. In addition, it is a little heavy as an applet, taking a relatively long loading time over the net. However, although its use as an applet does not enable defining new problems with new fitness functions, it enables extensive playing with many variations of an already existing problem type, by opening every aspect of the problem definition to the user. For example, any TSP test problem can be loaded through the 'Parameters' module. Used as an applet, the toolkit takes advantage of the Java cross-platform nature and the cross-world nature of the Internet, to bring a GA Playground to anyone interested in experimenting with genetic algorithms.
<p>
<A NAME="Requirements"></A><Center><U><H3>Browser Requirements and Loading Times</H3></U></Center>
The applet is written in JDK 1.1.5 and uses the new event model. Therefore it requires a browser that supports AWT 1.1. Currently (June 1998) this means MSIE 4.01, Netscape Communicator 4.05 Preview Release (The regular Communicator 4.05 supports only version 1.1.2) or Netscape Communicator 4.0+ with the JDK 1.1 patch. Other options are HotJava 1.1 or using the Java Plugin. <p>
<U>Download sites (all are free):</U><br>
<UL>
<LI>
<A HREF="http://developer.netscape.com/software/jdk/download.html">Netscape Communicator 4.05 Preview Release</A>
<LI>
<A HREF="http://www.microsoft.com/ie/download/">Microsoft Internet Explorer 4.01</A>
<LI><A HREF="http://www.javasoft.com/products/plugin/">Sun's Java Plugin</A>
<LI><A HREF="http://java.sun.com:80/products/hotjava/index.html">Hot Java</A>
</UL>
<p>
The applet is large and takes a relatively long time to load. It uses four jar files, the first is about 100K and the other three about 50K each. Please be patient until the loading process is finished. When the GA Playground is used as an application (the program's natural mode), and loaded locally and not from the Internet, the loading time is obviously very short.<p>
<A NAME="General Notes"></A><Center><U><H3>General Notes</H3></U></Center>
<A NAME="Alphabet"></A><U><H4>Alphabet</H4><br></U>
The implementation of the genetic algorithm uses a high alphabet to encode the chromosome's genes. In this implementation, each locus on the chromosome stands for a complete gene or variable. Since Java uses Unicode internally, the available range for the alleles of each gene is 64K, which provides an adequate resolution for most cases.<p>
<A NAME="Definition Files"></A><U><H4>Problem Definition - Definition Files</H4></U>
The input is defined by a Problem Definition file, an Ascii file formatted like a Windows Ini file. Two additional input files are optional: An alleles-definition file and a mapping file. These files are optional since in many cases the input they specify can be created automatically by the program.<p>
<A NAME="Source Modifications"></A><U><H4>Problem Definition - Source Modifications</H4></U>
The design of the program is modular, and each module is packaged separately as an easily replaceable (or extendable) class. Of the many classes that make the toolkit, only one should be handled by the user in defining a new problem. This is the GaaFunction class, that contains three methods: getValue, draw and createAllelesMap. The getValue method calculates the individual's fitness, and should obviously be written explicitly for each problem. The draw method is optional, and should be overwritten only if a graphic output is needed. The createAllelesMap is required only when a mapping file is not supplied, and the mapping table should be generated by the program.<p>
Besides these, any class can be extended or re-written to create a different genetic algorithm (e.g. the GaaMutation class or the GaaCrossover class)<p>
<A NAME="Special Mechanisms"></A><U><H4>Special GA Mechanisms</H4></U>
The implementation of the genetic algorithm follows the standard GA structure but it incorporates several less standard mechanisms:<p>
<A NAME="Kick"></A><B>1. An automatic 'Kick':</B> A sensor in the program monitors the evolutionary process, and when it finds that there has not been any advance in the recent N generations (N is user definable), it gives the population a 'Kick' and scrambles it a little (in a user defined manner). This mechanism helps against the GA tendency to get stuck at a mediocre local optimum.<p>
<A NAME="Kin Competition"></A><B>2. A kin-competition compensating factor:</B> If a population contains identical individuals, only one of them receives the nominally calculated fitness. The others are assigned decreased fitness values. This helps to maintain diversity in the population, and reduces the danger of the whole population being taken by a single, relatively superior, individual. The evolutionary justification for this mechanism (a justification is not really needed, but anyway), is that identical individuals compete over the same niche, so that although each might possess good genes, the very existence of the others makes it more difficult for him.<p>
<A NAME="Memory"></A><B>3. Memory: </B>
Each individual in a population owns both a chromosome (a solution string) and a memory string, where history data can be recorded. The use of the memory string is optional. If required, the memory maintenance code can be included in the fitness function.<p>
<A NAME="Extra Functions"></A><B>4. Pre & Post Breed Functions: </B>
These two functions (empty by default) are activated just before and just after breeding takes place (correspondingly). This enables to add any extra processing to the old population (preBreed) or to the new population (postBreed) during the process of creating a new generation<p>
<A NAME="UDF"></A><U><H4>Interactively (on-the-fly) defined functions</H4></U>
The GA Playground supports optimization of functions and expressions defined on-the-fly. The user can enter an expression of arbitrary length and complexity, with up to 20 variables, define range constraints for each variable, and let the program search for an optimized (minimum or maximum) solution. This option is available only in application mode (cannot be run in a browser).<p>
The interactive function optimization code is based on the Java Expressions Library (JEL), an amazing library that enables fast evaluation of dynamic string expressions. The library was written by Konstantin Metlov (metlov@fzu.cz), and its site is at http://galaxy.fzu.cz/JEL/.<p>
<A NAME="Continuous Reporting"></A><U><H4>Continuous Reporting</H4></U>
The applet user-interface supports three tools for monitoring the evolution process. Each is switchable, the trade off being performance (switched off) versus information (switched on). They are: The text window, where textual information is continuously displayed (when the text window is enabled), the graphic window that supports the draw method of the GaaFunction class when relevant (e.g. in TSP problems), and the Log window, that can gather information in the background and be displayed on request. All these tools can be toggled on or off anytime, including during execution.<p>
<A NAME="Graphic Display"></A><U><H4>Graphic Display</H4></U>
The program's Gui provides a graphic window which can optionally be used for displaying graphic representation of the evolutionary process. Problems of geometrical nature, such as TSP or resource allocation problems, are natural candidates for taking use of this option. To use the graphic option it is required to override the "draw" function in the user-modifiable GaaFunction file. The graphic display can be turned on or off at any time, including in the course of the evolution process.<p>
<A NAME="File IO"></A><U><H4>File Input/Output</H4></U>
<A NAME="Application IO"></A><B>1. Application Mode IO:</B>
Both input and ouput files can be saved to and loaded from disk.
Parameters that were modified interactively can be saved to a file,
and loaded later as a new problem definition. Parameter files (as well as
all other Ascii files) can be edited in a text editor, saved
(optionally under different names) and later used to define different problems<p>
Population of strings can be saved, together with the
their function and fitness values, to be studied and analyzed.
Saved population files can be loaded (completely or partially) into
the program, to define a specific population with known individuals. The population file can be edited in order to modify strings (chromosomes) or create new ones.<p>
Finally, the log screen that optionally stores information about the evolutionary process, can also be saved to disk for susequent examination.<p>
<A NAME="Applet IO"></A><B>2. Applet Mode IO:</B> When used as an applet, the GA Playground cannot access user's local
disk. Therefore input can only be modified through the multi-tabbed
Parameters module. This module supports editing of any aspect of the problem
definition, as long as it uses the same fitness function.
Output is limited to screen, but it can be copied and pasted to another
application through the clipboard (I am talking Windows here).<p>
<A NAME="Online Help"></A><U><H4>Online Help</H4></U>
The GA Playground assumes some familiarity with genetic algorithm programs, and the help is relatively concise. There are three help utilities<p>
<B>1. Online Help Screens:</B> Two basic help screens (General Help and Input Files Help) are accessible from within the program (Help menu).<p>
In addition there are two compact context-sensitive help mechanisms, which are particularly relevant to the parameters (input) panels:<p>
<B>2. Automatic Tool-Tip:</B> A short help string is automatically displayed in the status bar when the cursor is over a particular component (Textfield, label or button). This automatic mechanism can be toggled on or off through the Options menu.<p>
<B>3. Right-Mouse-Button click:</B> An additional short help string can be displayed in the status bar by clicking the right mouse button when the cursor is over a particular component. This second help tip complements the automatic help tip described above.<p>
<A NAME="Download"></A><U><H4>Download and Installation</H4></U>
The GA-Playground can be downloaded to be run from local hard disks. The program can be run either as an applet (from any browser supporting JDK 1.1.5), or as an application (running on a JDK 1.1.5 VM).<br>
Please download the <A HREF="GaPlayground.zip">GaPlayground.zip</A> (about 280K) and unzip it to any directory. The same files are used for both applet and application modes.<p>
<A NAME="Applet"></A><B>Applet Mode: </B>Just load any of the Html problem files into your (JDK 1.1.5 capable) browser. The file <B>gaa.html</B> (this file) contains an index of all the demo problems, and can be used to load any of them. However, any specific problem can be loaded directly into the browser (e.g. TspDemo.html). In any case, once the applet is loaded, any of the demo problems can be loaded through the Ga/Entry Screen menu.<p>
<A NAME="Application"></A><B>Application Mode: </B>The application is activated by the command:<br> <B>java GaaApplet [Parameters File]</B>.<br> The Parameter file name is optional: When not given the "All Demos" version (All.par) will be activated by default.<p>
Examples:<br>
To run the "All Demos" version: <B>java GaaApplet</B><br>
To run the TSP demo of Bavarian cities: <B>java GaaApplet bayg29.par</B><br><p>
<A NAME="Classpath"></A><B>Classpath (Application mode): </B>When used as application the three jar files of the GA Playground should be defined in the CLASSPATH variable. Each one should be entered separately.<p>
Example:<br>
If you unzipped the GaPlayground.zip file into C:\GAPL directory, your Classpath assignment should be similar to the following:<br>
set CLASSPATH=.;C:\GAPL\gaa.jar;C:\GAPL\ScsGrid.jar;C:\GAPL\tabsplitter.jar;
C:\jel.jar<p>
<A NAME="Batch"></A><B>Application Batch File: </B>On Windows you can create an icon that activates a batch file for running GA Playground as an application.<p>
The batch file should be similar to the following:<br>
CLASSPATH=.;tabsplitter.jar;ScsGrid.jar;jel.jar;gaa.jar<br>
java GaaApplet %1<br><p>
Assuming the batch file is named RunGaa.bat, entering "RunGaa" at the command prompt will activate GA Playground with the default (problem selection) mode, while entering e.g. "RunGaa TspDemo.par" will run the specific TspDemo problem.<p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -