jPoP

Abstract

For combinatorial optimization problems, which compute the optimal value of a multi-dimensional parameter function, several methods are known to be effective, such as Branch-and-Bound methods, Genetic Algorithm, etc. Since these methods can be massively parallelized and the granularities of computation tasks are easily controllable, they are considered to be suitable for executing on the Grid. However, distributed parallel programming on the Grid is quite complicated and furthermore setting up the Grid-wide computing environment is a heavy burden.

Here, we propose a system called jPoP, which makes it easy to develop and execute optimization-problem solvers on the Grid. To support the development, the jPoP provides a template class for each algorithm. And to reduce the cost of the setup, it automatically stages the user programs to the Grid environment.

Motivation

Combinatorial optimization problems are problems to find the optimal value of a multi-dimensional parameter function. There are lots of applications of this problems in the real world . There are several methods known to be effective for the problem, as follows.

Genetic Algorithm (GA)

GA is a search algorithm which imitates evolution of creatures. It treats solutions of a problem as genes and "evolves" them using "crossover", "mutation", and "natural selection".

Branch and Bound

Branch and bound method is a tree-based search algorithm. It divides a problem into several sub-problems and compute lower-bound for each sub-problem. If the lower-bound for a sub-problem is bigger than the feasible solution already known, the sub-problem can be pruned safely. By the pruning, this method achieves effective search in a huge search space.

Simulated Annealing(SA)

Simulated Annealing exploits an analogy between the way in which a metal cools and freezes into a minimum energy crystalline structure and the search for minimum in more general system.

Structure of jPoP

jPoP provides framework for the algorithms shown above. Users just implements very core elements of a algorithm extending template classes provided by jPoP. JPoP framework performs parallel execution using the user defined classes.

jPoP consists of the following 3 layers.

Template classes

Class templates represent core element of the specified algorithm. Users implement their own classes inheriting the template classes.

Algorithm Engine

The algorithm engine implements framework of the optimization algorithm and manages parallel execution.

Jojo

Jojo is a parallel communication library suitable for hierarchical grid environment. Jojo encapsulates lower layers such as communication channel and execution environments.

Template classes for jPoP-GA

Here, we show template classes for GA algorithm. Users implements their own classes inheriting these template classes.

In general, to define a GA system, following 3 entities have to be defined.

• Individual
• Environment to evaluate individual in
• Pool which controls GA process

Individual

To define individual, users have to give implementation of template class Individual and IndividualFactory.

Any Individual subclasses have to define the following methods.

/* initialize itself*/ public static void initializeProperties(); /* evaluates itself in Environment object stored in "env" field */ public double evaluate(); /* creates two descendants of itself and another individual. returns 2 elements array filled with the descendants. */ public Individual [] crossover(Individual); /* makes a copy of itself, mutates it and returns */ public Individual mutate();

IndividualFactory is a template class responsible for creation of individuals. Users have to implements the IndividualFactory interface shown below.

public interface individualFactory { /*initialize itself using the specified property */ void init(SilfProperties prop); /*creates new individual randomly */ Individual createRandomInitial(); /*returns specified numbers of randomly created individuals */ Individual [] getInitialSet(int count); }

Environment

Environment class represents environment in which individuals are evaluated. Environment is shared by all individuals and once initialized, it have to be immutable.

For example, assume TSP. Number of cities to visit and distance between each pair of cities are considered to be Environment. On the other hand, the order to visit each city should be stored in Individual subclass.

interface Environment extends Clonable Serializable{ /** initialize */ void init(SilfProperties prop); }

Pool

Pool class is responsible for generation manipulation in GA process. Since jPoP provides several build in pools, users do not have to implement Pool classes. Users can implement their own Pool class inheriting the following abstract class.

abstract public class Pool{ protected SilfProperties prop; protected boolean minimize; public void init() throws SilfException{ //dummy; } /*initialize */ abstract public void setInitialSet (IndividualHolder [] individuals); /* returns the optimal individual in the pool */ abstract public IndividualHolder getBest(); /* returns array of all individuals in the pool */ abstract public IndividualHolder [] getPopulation(); /* one generation forward */ abstract public void oneStep(); }

Issues

• By now, we have GA implementation only. We will implement Branch and bound and Simulated Annealing soon.

Related work

PopKern

PopKern is a generic combinatorial optimization problem solver implemented in C and KLIC (a kind of parallel logic language). It runs on SMP machine in parallel. The key idea of the PopKern is quite similar to the jPoP, but it does not support cluster or Grid environment.

MW

MW is a software framework which ease implementation of master-worker type application on the Grid. It uses Condor to manage its computational resources. Though, it is possible to implement combinatorial optimization problem solver using MW, users have to program the solver itself from scratch.