Genetic Algorithms for Optimal Graph Reduction
Hello all,
I am currently carrying out a project that involves using some genetic algorithms to solve optimal reduction Problems in a graphical term rewriting system. I want the algorithm to find the optimal positions for rewriting or reduction in this case
I need to represent chromosones in tree format to keep consistency with the graphs.
I was wondering if anyone could offer some ideas on the following (I don't want code!!):
1: How to get the input from keyboard as this requires a complex graph language? (Have considered Bison & Lex in C/C++)
2: What are the best mutation and crossover strategies for graphs?
3: Is there a java API that allows b-trees to be directly imported into the GA as it would really save me some time?
Thanks
Prashant
[818 byte] By [
PRASHPSG] at [2007-9-30 12:37:45]
> 1: How to get the input from keyboard as this requires
> a complex graph language? (Have considered Bison &
> Lex in C/C++)
>
Huh? Enter the graph as a list of edges where the endpoints of the edges are integers.
> 2: What are the best mutation and crossover strategies
> for graphs?
I don't think there is such a thing as "best" when you are talking about genetic algorithms.
You may find an algorithm that performs well on graphs that have a certain property, whether
you can determine that property to exploit it is another problem in itself.
>
> 3: Is there a java API that allows b-trees to be
> directly imported into the GA as it would really save
> me some time?
>
Does Java provide a GA API? If it is your own GA API then the question is most likely no. You might want to search source forge for APIs relating to genetic algorithms (GA).
Thanks for the reply,
There are several rules for appending nodes and deleting nodes that need to be applied and as such it is more of an abstact language I am trying to define.
There are nodes with special properties that will carry out specific functions for rewriting. I do see your point about using the edges with numbers to link the nodes. However its the nodes that worry me as some special nodes will have a specific functionality for creating the rewriting rules.
I need to use something like Bison or Yacc but a JAVA version to create an application that is capable defining a graph in Lambda Calculus terms for example its almost like I have to program the graph in as a chromosone. I do think it would be easier to generate random graphs though.
I looked at several Genetic APIs and apps for java
http://www.biojava.org
http://sourceforge.net/projects/j-a-g-a/
http://cs.gmu.edu/~eclab/projects/ecj/
http://jgap.sourceforge.net/
Just thought it might help others.
