12,349,785 members (26,625 online)
alternative version

25.1K views
36 bookmarked
Posted

# Genetic Algorithm for Knapsack Problem

, 18 Jun 2013 GPL3
 Rate this:
Solving knapsack problem using genetic algorithm

## Introduction

This example demonstrates a genetic algorithm that is designed to solve the problem introduced by this xkcd comic. The genetic algorithm is going to be implemented using GALex library.

A group of people walk into a restaurant and want to spend exactly \$15.05 on appetizers. They also want them as fast as possible. This leaves waiter with an NP-hard problem to solve, a variation of knapsack problem.

The problem waiter have to solve is selection of items from the menu, so they cost exactly the amount customers specified. This problem by itself is NP-hard, but that is not enough for the snarky customers. They want it as fast as possible. So the waiter cannot select any combination that satisfy price requirement. He must find all the combinations, so he can choose the one which will take the least amount of time to make.

## Chromosome

Defining chromosome representation that is going to be used by the genetic algorithm as well as designing good crossover and mutation operations are crucial steps and they are most often specific to the problem that has to be solved.

### Representation

One of the first things that should be done when designing a genetic algorithm is choosing the adequate representation for the solutions. There are several ways to encode a solution. Some of the possible representations are:

• unordered linked list where list nodes contains items that should be served
• array that stores count of items that should be served

Array representation

Chosen representation will greatly influence the design of other genetic operations such as crossover or mutation operation. For this example the linked list representation is chosen.

One advantage of the representation is that it allows genetic algorithm to optimize representation itself. Crossover can shuffle blocks of items around the chromosome without affecting its fitness value. This way genetic algorithm can group good combinations of items close together. These combinations are known as building block. Such grouping reduces the chances of building blocks disruption, which is a good thing since such disruptions most often degrade quality of a solution and its fitness value.

Each node in the list will store index of the item on the menu. Since each node can have fixed set of values, `GaAlleleGene` are going to be used to represent genes. This gene stores allele set in addition to gene value. Allele set is a set of values that are allowed for gene to have them. `GaAlleleGene` is a complex type gene so `GaAdvanceListChromosome` class has to be used as chromosome type. So with a few `typedef`s chromosome representation is almost ready:

```typedef Chromosome::Representation::GaAlleleGene<int> XkcdGene;
typedef Common::Data::GaList<XkcdGene> XkcdGeneList;

int, Chromosome::Representation::GaAlleleGene>::GaType XkcdChromosome;
```

Next thing that needs to be defined is chromosome configuration block (CCB). CCB will contain list of appetizers, with their prices and time required to make, as well as allele set for chromosomes' genes.

Definition of appetizer:

```struct Appetizer
{
std::string _name;
float _price;
float _time;

Appetizer();
Appetizer(const std::string& name,
float price,
float time);
};
```

Definition of CCB:

```class XkcdConfigBlock : public Chromosome::GaChromosomeConfigBlock
{
private:
Common::Data::GaSingleDimensionArray<Appetizer> _appetizers;
Chromosome::Representation::GaIntervalAlleleSet<int> _interval;

public:
XkcdConfigBlock(
const Common::Data::GaSingleDimensionArray<Appetizer>& appetizers) :
_appetizers( appetizers ),
_interval (
Chromosome::Representation::GaValueIntervalBounds<int>(
0, appetizers.GetSize() - 1 ),
Chromosome::Representation::GaValueIntervalBounds<int>(
0, appetizers.GetSize() - 1 ),
GaGlobalRandomIntegerGenerator ) { }

XkcdConfigBlock(const XkcdConfigBlock& rhs) :
GaChromosomeConfigBlock(rhs),
_appetizers(rhs._appetizers),
_interval(rhs._interval) { }

virtual GaChromosomeConfigBlock* GACALL Clone() const
{ return new XkcdConfigBlock( *this ); }
};
```

`XkcdConfigBlock` class that inherits `GaChromosomeConfigBlock` represents CCB specific for this problem. Notice that user defined CCBs must implement `Clone` method and it has to have copy constructor.

Allele set that is used is `GaIntervalAlleleSet`. This set contains all values in the defined range. This is enough since the values should be indices of items in appetizer list. Every allele set also takes set of inverted values, required by some genetic operations. In this case it is the same set.

Now that the chromosome type is ready following genetic operations have to be defined:

• chromosome initialization
• chromosome comparator
• fitness operation
• crossover operation
• mutation operation

### Chromosome Initialization

The approach for chromosome initialization is simple: determine random number of items, and then randomly select items until the desired count is reached. In case that new chromosome is needed for crossover operation and empty chromosome is returned. The operation also sets the CCB for the chromosome.

`XkcdInitializator` class is responsible for creation of new chromosomes. It is inherited from `GaInitializator` which represents the base class for user-defined initializators. `operator ()` is called by the library to create and initialize new chromosome.

```class XkcdInitializator : public Chromosome::GaInitializator
{
public:
virtual Chromosome::GaChromosomePtr GACALL operator ()(
bool empty,
const Chromosome::GaInitializatorParams& parameters,
Common::Memory::GaSmartPtr<
Chromosome::GaChromosomeConfigBlock> configBlock) const;

virtual Common::GaParameters* GACALL CreateParameters() const
{ return NULL; }
};
```

Since operation parameters are not used by this implementation of the initializator `CreateParameters` returns `NULL`.

### Chromosome Comparator

Chromosome comparator is implemented by `XkcdChromosomeComparator` class and it is inherited from `XkcdChromosomeComparator` which is base class for user-defined comparators.

```class XkcdChromosomeComparator :
public Chromosome::GaChromosomeComparator
{
public:

virtual float GACALL operator ()(
const Chromosome::GaChromosome& chromosome1,
const Chromosome::GaChromosome& chromosome2,
const Chromosome::GaChromosomeComparatorParams& parameters) const
{ return Equal( chromosome1, chromosome2, parameters ) ? 0.0f : 1.0f; }

virtual bool GACALL Equal(
const Chromosome::GaChromosome& chromosome1,
const Chromosome::GaChromosome& chromosome2,
const Chromosome::GaChromosomeComparatorParams& parameters) const
{ return ( (const XkcdChromosome&)chromosome1 ).GetGenes() ==
( (const XkcdChromosome&)chromosome2 ).GetGenes(); }

virtual Common::GaParameters* GACALL CreateParameters() const
{ return NULL; }
};
```

This implementation use simple comparison method defined by the list container, and returns `true`/`false` (or `1`/`0`). In case the fitness sharing scaling (`GaShareFitnessScaling`) should used by the algorithm, different implementation is required and comparison have to return rate of similarity between the chromosomes.

### Fitness Operation

Fitness operation is responsible for calculating fitness value of a chromosome. Stated problem has two criteria: cost of appetizers and time needed to make them, so the genetic algorithm should take both of these into account when calculating fitness of the chromosome. Since price is more important criterion then time in this case, weights can be assigned to these values accordingly and real multi-objective optimization with pareto sets is not required. Taking into the account all the values and their weights fitness function should look like this:

Fitness function: f - fitness value, wp - weight of price criterion, wt - weight of time criterion, tp - target price, n - number of appetizer, api - price of i-th appetizer, ati - required time to make i-th appetizer

Since the price is more important higher weight should assigned to wp then to wt. In this example wp is set to `2.0` and wt is set to `1.0`.

Wight-based fitness value representation, available in library and implemented by `GaWeightedFitness` class, is nicely fitted for this example. It can preserve values of both criteria (price and time) so they can be displayed, weights can be assigned to these values by the fitness parameters and the implementation calculates total fitness automatically by summing weighted values.

```typedef Fitness::Representation::GaWeightedFitness<float, float> XkcdFitness;
```

That is enough to have fitness value representation that can be used by fitness operation and the rest of the library.

GALex has two different approaches to evaluate fitness value of chromosomes:

1. population-based - fitness of all chromosomes in population is evaluated at once. This approach has to be used when fitness function of a chromosome is not independent from other chromosomes in population.
2. individual-based - fitness of a chromosome is evaluated independently from other chromosomes. This approach is preferred as it allows library to optimize other genetic operations such as selection and coupling...

Fitness function for this problem is defined in such way that it can use individual based approach.

Operation is implemented by `XkcdFitnessOperation` class and it inherits `GaChromosomeFitnessOperation` which is base class for individual-based fitness operations. Since there is targeted price, it must be specified by operation parameters which are implemented by `XkcdFitnessOperationParams` class that uses `GaFitnessOperationParams` as base.

```class XkcdFitnessOperationParams :
public Fitness::GaFitnessOperationParams
{
private:
float _targetPrice;

public:
XkcdFitnessOperationParams(float targetPrice) :
_targetPrice( targetPrice ) { }

XkcdFitnessOperationParams(const XkcdFitnessOperationParams& params) :
_targetPrice( params._targetPrice ) { }

virtual GaParameters* GACALL Clone() const
{ return new XkcdFitnessOperationParams( *this ); }

inline float GACALL GetTargetPrice() const { return _targetPrice; }

inline void GACALL SetTargetPrice(float price)
{ _targetPrice = price; }
};

class XkcdFitnessOperation :
public Chromosome::GaChromosomeFitnessOperation
{
public:
virtual Fitness::GaFitness* GACALL
CreateFitnessObject(
Common::Memory::GaSmartPtr<
const Fitness::GaFitnessParams> params) const
{ return new XkcdFitness( params ); }

virtual void GACALL operator ()(const GaObjectType& object,
Fitness::GaFitness& fitness,
const Fitness::GaFitnessOperationParams& operationParams) const;

virtual Common::GaParameters* GACALL CreateParameters() const
{ return new XkcdFitnessOperationParams(); }
};
```

`CreateFitnessObject` is called by the library when it needs to creating fitness value object and code `operator ()` is responsible for evaluationg fitness value of the chromosome.

### Crossover Operation

The purpose of crossover operation is to produce new solution by combining existing ones. Implementation of crossover operation depends on the representation. As it was already discussed, the algorithm uses linked-list representation, so simple single-point crossover operation can be used:

Crossover operation

The library already has implementation of such crossover operation. It is represented by `GaListMultipointCrossover` class.

### Mutation Operation

Mutation operation is responsible for retaining genetic diversity of the chromosomes in the population. It is done by randomly changing genes in newly produced chromosomes:

Mutation operation

The operation is implemented by `XkcdMutationOperation` class. It inherits `GaMutationOperation` which is base for all user-defined mutation operations. `operator ()` is responsible for performing mutation on the chromosome. This operation requires parameters that tell it how many genes it should change for which `GaMutationSizeParams` class is used.

```class XkcdMutationOperation : public Chromosome::GaMutationOperation
{
public:

virtual void GACALL operator ()(Chromosome::GaChromosome& chromosome,
const Chromosome::GaMutationParams& parameters) const;

virtual Common::GaParameters* GACALL CreateParameters() const
{ return new Chromosome::GaMutationSizeParams(); }
};
```

### Mating Operation

Mating operation controls production cycle of new chromosomes. Cycle includes all the genetic operations that should executed to produce new chromosome and their parameters. Basic cycle consists of invoking crossover operation to produce new chromosomes and invoking mutation operation on those chromosomes. This cycle is implemented in the library by `GaBasicMatingOperation` class. User can customize production cycle by implementing custom mating operation. `GaMatingOperation` is base class for all mating operations.

## Putting the Pieces Together

The final stage is to a define population, select the appropriate algorithm and chose selection and replacement operations. Algorithm configuration and parameters:

 mutation probability: 30% mutation size: 1 gene only accept mutations that improve fitness: yes crossover probability: 80% crossover points: 1 algorithm type: incremental (overlapping population) population size: 32 chromosomes sorted population: yes fitness sorting: maximization fitness weights: 2.0, 1.0 selection type: roulette wheel selection size: 8 coupling type: none (selection performs mating) number of offspring to produce: 8 scaling type: no scaling replacement type: replace worst chromosomes to replace: 8 stop criterion type: fitness change stop criterion depth: 1000 generations

The code that puts all the pieces together to create genetic algorithm looks like this:

```// create mating operation with:
// crossover - 80% probability, 2 offspring, 1 crossover point
// mutation - 30% probability, accept only improving mutations, 1 gene
Chromosome::CrossoverOperations::GaListMultipointCrossover crossover;
Problems::XKCD::XkcdMutationOperation mutation;
Chromosome::MatingOperations::GaBasicMatingOperation mating;
Chromosome::GaMatingConfig matingConfiguration(
Chromosome::GaCrossoverSetup( &crossover,
&Chromosome::GaCrossoverPointParams( 0.8f, 2, 1 ), NULL ),
Chromosome::GaMutationSetup( &mutation,
&Chromosome::GaMutationSizeParams( 0.3f, true, 1L ), NULL ) );

Problems::XKCD::XkcdConfigBlock::Appetizer appetizers[] =
{
Problems::XKCD::XkcdConfigBlock::Appetizer("mixed fruit", 2.15f, 3),
Problems::XKCD::XkcdConfigBlock::Appetizer("french fries", 2.75f, 2),
Problems::XKCD::XkcdConfigBlock::Appetizer("hot wings", 3.55f, 3),
Problems::XKCD::XkcdConfigBlock::Appetizer("mozzarella sticks", 4.20f, 4),
Problems::XKCD::XkcdConfigBlock::Appetizer("sampler plate", 5.80f, 7),
};

// create chromosome initializator
Problems::XKCD::XkcdInitializator initializator;
Chromosome::GaInitializatorSetup initializatorSetup( &initializator,
NULL, &Chromosome::GaInitializatorConfig(
&Problems::XKCD::XkcdConfigBlock(
Common::Data::GaSingleDimensionArray<
Problems::XKCD::XkcdConfigBlock::Appetizer>( appetizers, 6 ) ) ) );

// create fitness comparator for maximizing fitness value
Fitness::Comparators::GaSimpleComparator fitnessComparator;
Fitness::GaFitnessComparatorSetup fitnessComparatorSetup(
&fitnessComparator,
&Fitness::Comparators::GaSimpleComparatorParams(
Fitness::Comparators::GACT_MAXIMIZE_ALL ), NULL );

// fitness operation
Problems::XKCD::XkcdFitnessOperation fitnessOperation;
Population::GaCombinedFitnessOperation populationFitnessOperation(
&fitnessOperation );

// create population statistics trackers
// for fitness values and population size
Population::GaPopulationSizeTracker sizeTracker;
Population::GaRawFitnessTracker rawTracker;
Algorithm::Stubs::GaSimpleGAStub::GaStatTrackersCollection trackers;
trackers[ Population::GaPopulationSizeTracker::TRACKER_ID ] =  &sizeTracker;
trackers[ Population::GaRawFitnessTracker::TRACKER_ID ] =  &rawTracker;
trackers[ Population::GaScaledFitnessTracker::TRACKER_ID ] =  &scaledTracker;

// create selection operation that:
// uses roulette wheel method and
// selects 8 parents and produces 8 offspring chromosomes
// using defined mating
Population::SelectionOperations::GaRouletteWheelSelection selection;
Population::GaSelectionSetup selectionSetup( &selection,
&Population::GaCouplingConfig(
Chromosome::GaMatingSetup( &mating, NULL, &matingConfiguration ) ) );

// create replacement operation that:
// replaces 8 worst chromosomes in the population
Population::ReplacementOperations::GaWorstReplacement replacement;
Population::GaReplacementSetup replacementSetup( &replacement,
&Population::GaReplacementParams( 8 ),
&Population::GaReplacementConfig(
Chromosome::GaChromosomeComparatorSetup(
&chromosomeComparator, NULL, NULL ) ));

// creates scaling operation that just copies raw fitness value
Population::ScalingOperations::GaNoScaling scaling;
Population::GaScalingSetup scalingSetup( &scaling, NULL,
&Population::GaScalingConfig() );

// weights used to calculate fitness value
float fitnessWights[] = { 2.0f, 1.0f };

// create simple algorithm stub:
// population - 32 chromosomes, 0 crowding size, sort by raw fitness
Algorithm::Stubs::GaSimpleGAStub simpleGA(
WDID_POPULATION,
WDID_POPULATION_STATS,
initializatorSetup,
Population::GaPopulationFitnessOperationSetup(
&populationFitnessOperation,
&Problems::XKCD::XkcdFitnessOperationParams( targetPrice ),
&Fitness::GaFitnessOperationConfig(
&Fitness::Representation::GaWeightedFitnessParams<float>(
fitnessWights, 2 ) ) ),
fitnessComparatorSetup,
Population::GaPopulationParams( 32, 0,
Population::GaPopulationParams::GAPFO_FILL_ON_INIT ),
trackers,
Chromosome::GaMatingSetup(),
selectionSetup,
Population::GaCouplingSetup(),
replacementSetup,
Population::GaScalingSetup(),
Population::GaFitnessComparatorSortingCriteria( fitnessComparatorSetup,
Population::GaChromosomeStorage::GAFT_RAW ) );

// create workflow
Common::Workflows::GaWorkflow workflow( NULL );
workflow.RemoveConnection(
*workflow.GetFirstStep()->GetOutboundConnections().begin(), true );

// connect algorithm stub to workflow
Common::Workflows::GaWorkflowBarrier* br1 =
new Common::Workflows::GaWorkflowBarrier();
simpleGA.Connect( workflow.GetFirstStep(), br1 );

Common::Workflows::GaBranchGroup* bg1 =
(Common::Workflows::GaBranchGroup*)workflow.ConnectSteps(
br1, workflow.GetLastStep(), 0 );

// create stop criteria that will stop the algorithm if:
// raw fitness of the best chromosome in the population
// has not been changed for the last 1000 generations.
Algorithm::StopCriteria::GaStatsChangesCriterion stopCriterion;
Algorithm::StopCriteria::GaStopCriterionStep* stopStep =
new Algorithm::StopCriteria::GaStopCriterionStep(
Algorithm::StopCriteria::GaStopCriterionSetup(
&stopCriterion,
&Algorithm::StopCriteria::GaStatsChangesCriterionParams(
workflow.GetWorkflowData(), WDID_POPULATION_STATS );

// connect stop criterion to workflow and algorithm stub
Common::Workflows::GaBranchGroupTransition* bt1 =
new Common::Workflows::GaBranchGroupTransition();
bg1->GetBranchGroupFlow()->SetFirstStep( stopStep );
bg1->GetBranchGroupFlow()->ConnectSteps( stopStep, bt1, 0 );
workflow.ConnectSteps( bt1, simpleGA.GetStubFlow().GetFirstStep(), 1 );

// subscribe handler to event raised before new generation cycle begins
workflow.GetWorkflowData(), WDID_POPULATION );
Population::GaPopulation::GAPE_NEW_GENERATION, &newGenHandler );

// start algorithm and wait for it to finish
workflow.Start();
workflow.Wait();
```

## Results

The following section presents results of a single run for target price of \$15.05. It shows progress of chromosomes' fitness values and their components during the run. X-axis represents generations of the population and Y-axis represents fitness value or one of its component.

Weighted fitness value of the best chromosome and the worst chromosome in population and average value

Price component of the best chromosome in the population - how far it is off the targeted price

Time component of the best chromosome in the population - how much time it is needed to make appetizers

## History

• 18 Jun 2013 - Results and statistics added
• 17 Jun 2013 - Original article posted

## Share

 Software Developer Serbia
No Biography provided

## You may also be interested in...

 First Prev Next
 Relating running of exe file Jack_1215-Dec-15 7:17 Jack_121 5-Dec-15 7:17