How to initialize Chromosomes in an Evolutionary Algorithm to solve an LP/ILP or general COS on real variables?

Question

I am working on a Java framework for Optimization Problems. So far, I have implemented lp_solve and GLPK and therefore I can handle linear problems (LPs) and integer linear problems (ILPs). Now I want to provide the possibility of using Evolutionary Algorithms as solver in order to be able to handle problems with non-linear constraints or a non-linear objective function. In general to handle constraint optimization problems (COS). I found the Apache commons genetic package for genetic algorithms and started implementing a Genetic Algorithm.

A chromosome in my algorithm represents a solution to the Optimization problem, i.e. it consists of a map Variable -> Number. Now, in the first population, I would like to randomly create a solution and start evolving from there. Hence, I need to find random values for the variables. I have access to the lower and upper Bound of a variable and whether its domain are the Integers are the Reals. Hence I initiate the variables in the following way:

//Create a Random Number generator
Random generator = new Random();

//Create a new Map to store the variables and their assigned values
Map<String,Number> newRepresentation = new HashMap<String,Number>();

//Iterate over all variables from the problem
for (Entry<String,Variable> entry : problem.getVariables().entrySet()) {
    Variable variable = entry.getValue();
    Number uB = variable.getUpperBound();
    Number lB = variable.getLowerBound();
    //Create a random value for this variable
    Number randomValue = (generator.nextDouble() * (uB.doubleValue() - lB.doubleValue())) + lB.doubleValue();
    //If the variable has Integers as its domain, make the random value an Integer
    if (variable.getType() == OptVarType.INTEGER) randomValue = randomValue.intValue();
    newRepresentation.put(variable.getName(), randomValue);
}

This should give me a map newRepresentation with an assignment of all variables to random numbers. However, if the variable is not restricted, i.e. the lower bound equals 0 and the upper bound equals Integer.MAX_VALUE, I do never get values close to the lower bound. For example, I have the problem

max 3x+4y
s.t.
x+2y <= 14
3x-y >= 0
x-y <= 2
x in {0,...,2147483647}
y in {0,...,2147483647}

Then the optimal solution is x=6, y=4. But the variables are initialized by my EA as:

A new Population has been initiated: {y=1430866067, x=1616622921}
A new Population has been initiated: {y=1483081480, x=1389387196}
A new Population has been initiated: {y=242558338, x=376547119}
A new Population has been initiated: {y=1861689859, x=959676986}
...

The value does never get close to the lower bound, where the optimal solution is located. Hence, my EA does not, even after minutes of searching, find a solution that is at least close to the optimal solution.

Question: How can I modify the initiation of chromosomes, such that the values are evenly distributed over the whole search space?

Answer 1

First, I have thought over whether your integer values are still evenly distributed after your tranformation.

Example:

You want to create an integer between 5 and 10. So you create a uniformly distributed double in that interval (which works fine with your code) and the likeliness of it being in [5,5.5) is equal to the chance of it being in [5.5,6), in [6,6.5], ... , [9.5,10). Now, to convert it to integer, you floor the value, mapping two of the intervals I described to each possible integer value. So this seems fine to me.

I have also performed a brief test and it works fine for me. So I only see two possible reasons for your problem:

1. The random number generator is broken. (which is unlikely if you use a standard JDK)
2. You perform too few trials to also get low start values - the interval is quite large.

EDIT: I have looked at the documentation of the Number class. The conversion to integer is free to use either truncation OR rounding. If it does use rounding, the random integer values are no longer uniformly distributed, so you should explicitly floor the double value.