examples.constraint
Class ConstraintExample

java.lang.Object
  examples.constraint.ConstraintExample

public class ConstraintExample
extends java.lang.Object

This class provides an implementation of the classic "Make change" problem using a genetic algorithm. The goal of the problem is to provide a specified amount of change (from a cash purchase) in the fewest coins possible. This example implementation uses American currency (quarters, dimes, nickels, and pennies).

This example may be seen as somewhat significant because it demonstrates the use of a genetic algorithm in a less-than-optimal problem space. The genetic algorithm does best when there is a smooth slope of fitness over the problem space towards the optimum solution. This problem exhibits a more choppy space with more local optima. However, as can be seen from running this example, the genetic algorithm still will get the correct (or a very close) answer virtually everytime.

Since:

3.6.2

Field Summary

static EvolutionMonitor

m_monitor

Constructor Summary

ConstraintExample()

Method Summary

static void	main(java.lang.String[] args) Main method.
static void	makeChangeForAmount(int a_targetChangeAmount, boolean a_doMonitor) Executes the genetic algorithm to determine the minimum number of coins necessary to make up the given target amount of change.
static boolean	uniqueChromosomes(Population a_pop)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

m_monitor

public static EvolutionMonitor m_monitor

Constructor Detail

ConstraintExample

public ConstraintExample()

Method Detail

makeChangeForAmount

public static void makeChangeForAmount(int a_targetChangeAmount,
                                       boolean a_doMonitor)
                                throws java.lang.Exception

Executes the genetic algorithm to determine the minimum number of coins necessary to make up the given target amount of change. The solution will then be written to System.out.

Parameters:

a_targetChangeAmount - the target amount of change for which this method is attempting to produce the minimum number of coins

a_doMonitor - true: turn on monitoring for later evaluation of evolution progress

Throws:

java.lang.Exception

Since:

1.0

main

public static void main(java.lang.String[] args)
                 throws java.lang.Exception

Main method. A single command-line argument is expected, which is the amount of change to create (in other words, 75 would be equal to 75 cents).

Parameters:

args - amount of change in cents to create

Throws:

java.lang.Exception

Since:

1.0

uniqueChromosomes

public static boolean uniqueChromosomes(Population a_pop)

Parameters:

a_pop - the population to verify

Returns:

true if all chromosomes in the populationa are unique

Since:

3.3.1