Dear colleagues,
We are pleased to announce Multi Expression Programming (MEP), a new
evolutionary technique that performs significantly better than Gene
Expression Programming (GEP).
The paper about MEP may be downloaded from
www.mep.cs.ubbcluj.ro
Multi-Expression Programming is intended for solving computationally
difficult problems. MEP individuals are linear entities that encode
complex computer programs. A MEP individual may encode multiple
solutions of the current problem. Usually the best solution is chosen for
fitness calculation.
MEP may used for solving computationally difficult problems like symbolic
regression, game strategies discovering, generating heuristics etc.
MEP has some evident advantages with respect to other GP techniques. For
instance MEP supplies the shortest linear representation. Moreover, the
MEP genome does not contain non-coding sequences.
MEP provides a simple way to discover game strategies. Consider a
two-player game. The evaluation of a game configuration is realized using
a computer program (a function) that is evolved by MEP algorithm.
In a training stage MEP evolves a computer program (a function) those
output is the quality of each possible game configuration. This function
describes the MEP strategy used for game playing purposes.
MEP strategy evaluates each game configuration that can be reached from
the current state in one move. The best move is selected using this
evaluation.
MEP algorithm was tested for Tic-Tac-Toe, a simple to describe but an
enough complex game.
One of the most important applications of MEP is discovering heuristics
for solving computationally difficult (Nondeterminist Polynomial -
Complete (NP-Complete)) problems. Instead of solving a single instance of
the problem the aim is here to discover a heuristic that solves the entire
class of problems.
In this paper we indicate how MEP can be used to discover a heuristic
procedure for solving TSP problem (or Hamiltonian cycle problem). The idea
is similar with that used for discovering games strategy. In the proposed
approach the Hamiltonian cycle starts with a randomly selected node. Each
node reachable from the current node in one step is evaluated using the
function (computer program) evolved by MEP algorithm. The best node is
chosen and is added to the already founded path. The algorithm stops when
the path contains all graph nodes.
MEP algorithm was trained for graphs having 3 to 50 nodes.
MEP technique is used to learn a function f that is directly used for
building the optimum path. The corresponding learning process has a
remarkable quality: the evolved (learned) heuristic works very well for
data sets much larger than the training set.
MEP technique may be used for solving other difficult problems like
handwritten character recognition, natural language processing, voice
synthesis, automated code generation, forecasting, discovering
recurrence relations for dynamic programming, theorem proving etc.
MEP technique is compared with GEP using a well-known benchmark problem.
The results suggest that MEP algorithm performs substantially better than
GEP on the considered examples.
Researchers from all over the world may use this new and powerfull
paradigm for solving difficult problems in their fields of interest.
Sincerly yours,
Mihai Oltean
D. Dumitrescu
|