Skip to content

Latest commit

 

History

History
355 lines (284 loc) · 25.8 KB

README.md

File metadata and controls

355 lines (284 loc) · 25.8 KB
Raw

GA_Lib and WOA_Lib

General Purpose GA and WOA Library using CUDA C++

About

GA_Lib and WOA_Lib is C++ Library for GA (Genetic Algorithm) and WOA (Whale Optimization Algorithm) with the support of NVIDIA CUDA. This library can only support C++ and require user to install CUDA beforehand.

Requirements

  1. NVIDIA Graphics Card that is listed in CUDA Capable Hardware (See CUDA Enabled Products).
  2. CUDA Toolkit 9.0 or more.
  3. Visual Studio 2015 or more with C++.

Features

  • General Metaheuristic Problem to be Solved — Any problems that can be solved using Evolutionary Algorithms, especially metaheuristic problems, can be solved using this library. The given examples inside the library shows two of general metaheuristic problems: Sudoku and TSP, to be solved using this library. As long as the problem can be represented into individual and the fitness can be calculated, GA_Lib and WOA_Lib are the right things to be used to solve the given problems.

  • Clean, Object-Oriented Library Design — Object oriented shows that all things can be turned into object. GA_Lib and WOA_Lib are using clean OOP Design with implementation of abstract class to make it easier for user to implement GA and WOA on real problems.

  • Easy, Short Implementation — It is many people wish to solve any problems using easiest method. With GA_Lib and WOA_lib, user can implement GA and WOA using the easiest means, with some simple understanding and short implementation of code. Of course, this depends on the scale of problems.

  • Fast, GPU-Programming Based Library — Speed is an essential matters for all libraries these days. It also applies for GA_Lib and WOA_Lib. These 2 libraries are based on GPU-Programming, especially NVIDIA CUDA, to run the code. It is required things to have if user want to use these libraries.

  • Full and Complete Documentation — GA_Lib and WOA_Lib provides full documentation of all the features inside library to be used.

Class Hierarchy

GA_Lib (T indicates type of chromosomes initialized by user)

List of things inside library can be accessed by user:

1. Enumeration

  • StopCriteria (Automatic set when the constructor is called) :

    • GenerationComplete(0)
      For every loop, new childs are produced and some of chromosomes are eliminated, and the currentGeneration number is increased. By setting the stopCriteria into GenerationComplete, the process is terminated on number of generation, no matter if the solution is found or not.
    • FitnessBoundaryAchieved(1)
      The solution is found if the best fitness in generation met fitnessBoundary number. The termination process is not based on generation but based on whether the best fitness met fitnessBoundary number or not.
    • FitnessAndGenerationCheck(2)
      The combination of two previous Stop Criteria. The process is terminated if generation number is met OR bestFitness number is equal or more than fitnessBoundary.

    Besides 3 Stop Criteria that can be set by user, if in 100.000 generation, the best fitness doesn't change, the process will be automatically terminated.

  • CrossoverType:

    • OnePointCrossover(0)
      In One Point Crossover, one number is randomized between zero until maximum size of chromosome. That number becomes a divider for the child, whether to take gen value from parent 1 or parent 2.

      One Point Crossover

    • MultiPointCrossover(1)
      Multi Point Crossover has same steps as One Point Crossover. The difference is the number that's randomized is not just one, but two. This number acts as divider, and for each gen, if gen index is between the two number, the gen of child will be inherited from one parent, otherwise the gen will be inherited from another parent.

      Multi Point Crossover

    • UniformCrossover(2)
      In Uniform Crossover, both parent has 50% chance to inherit their gen to the child. This applies for every gen of chromosomes.

      Uniform Crossover

    • PMXCrossover(3)
      PMX Crossover is used for permutation problem, means that the problem needs all value of gens inside the chromosome to be different value to each other. User can't apply this crossover if there are identical values between 2 gen inside chromosome. PMX Crossover uses maps and values system. First, 2 numbers will be randomized and act as divider, same with Multi Point Crossover. The gen between 2 randomized numbers will be taken from one parent while the gen outside 2 randomized numbers will be taken from another parent. If the gen outside divider is the same as the gen inside the divider, the algorithm will search the same number inside the map system, and change the number based on stored values of map.

      PMX Crossover

    • Order1Crossover(4)
      Same with PMX Crossover, Order1 Crossover is used for permutation problem. User can't apply this crossover if there are identical values between 2 gen inside chromosome. With 2 randomized numbers act as divider, the next process is iteration for every gen outside the divider, starting from gen index next to last index of divider. All unoccupied gen (gen with value which is not inside divider) will be placed in sequence till all child's gen is filled with value.

      Order1 Crossover

    The number of child's that will be produced is chromosomePerGeneration * 2. crossoverRate is used to determined whether the next 2 childs to be produced is from crossover that's chosen by user, or from copying the parents.

  • MutationType:

    • RandomResetting(0)
      Random Resetting can only be done if user implements virtual void randomChromosome. One gen inside child will be changed into randomized value.
    • SwapMutation(1)
      Swap Mutation do swapping operation on 2 gen's child. The indexes of gen that are being swapped is randomized.

      Swap Mutation

    • ScrambleMutation(2)
      Scramble Mutation takes 2 randomized number to act as divider, then every gen inside the divider will be scrambled (swap many times).

      Scramble Mutation

    • InversionMutation(3)
      Inversion Mutation takes 2 randomized numbers to act as divider, and inverse the gen inside the divider.

      Inversion Mutation

    For mutation process, every new child has chances to be mutated or not. This chance percentages is taken from mutationRate.

  • SelectionType:

    • RouletteWheelSelection(0)
      Every chromosomes has a number of percentages to be chosen as parent, based on their fitness. In Roulette Wheel Selection, every fitness will be added, a number will be randomized between 0 and total fitness, and based on that, a chromosome will be chosen based on number's result.

      Roulette Wheel Selection

    • TournamentSelection(1)
      With tournament selection, a set of chromosomes will be chosen to be contested. The chosen chromosomes is purely randomized. After a set of chromosomes is defined, the chromosome with best fitness will be chosen as parent.

      Tournament Selection

    • RankSelection(2)
      Same with Roulette Wheel Selection, Rank Selection use fitness of chromosomes as a number of percentage for every chromosome. The difference is, it is not the fitness values that is being used for selecting parent, but the rank of fitness values is being used. It means no matter how big the gap of fitnesses of chromosomes, the number of chances is always the same. The rank is all that matters.

      Rank Selection

2. Constructor

  • GA_Lib(int size) : default parameters are chromosomePerGeneration = 200, generation = 10000, mutationRate = 0.15, crossoverRate = 0.35, crossoverType = OnePointCrossover, mutationType = RandomResetting, selectionType = _RouletteWheelSelection.
  • GA_Lib(long generation, int size, long chromosomePerGeneration, float mutationRate, float crossoverRate , CrossoverType crossoverType, MutationType mutationType , SelectionType selectionType) : stopCriteria is automatically set to GenerationComplete.
  • GA_Lib(float fitnessBoundary, int size, long chromosomePerGeneration, float mutationRate, float crossoverRate , CrossoverType crossoverType, MutationType mutationType , SelectionType selectionType) : stopCriteria is automatically set to FitnessBoundaryAchieved.
  • GA_Lib(long generation, float fitnessBoundary, int size, long chromosomePerGeneration, float mutationRate , float crossoverRate, CrossoverType crossoverType, MutationType mutationType , SelectionType selectionType) : stopCriteria is automatically set to FitnessAndGenerationCheck.
  • ~GA_Lib()

3. Accessor and Mutator

  • get and set generation : long type, the number of generation inside the process, process terminated if currentGeneration number has passed generation number (if using GenerationComplete or FitnessAndGenerationCheck for stopCriteria).
  • get and set fitnessBoundary : float type, the number of maximum fitness inside the process, process terminated if bestFitness number has passed fitnessBoundary number (if using FitnessBoundaryAchieved or FitnessAndGenerationCheck for stopCriteria).
  • get and set chromosomePerGeneration : int type, the amount of chromosome per generation to be operated with Selection, Crossover, and Mutation in every loop.
  • get and set crossoverRate : float type, how much percentage to do crossover.
  • get and set mutationRate : float type, how much percentage to do mutation on new child.
  • get and set stopCriteria : short type, chosen Stop Criteria based on StopCriteria enumeration.
  • get and set crossoverType : short type, chosen Crossover Type based on CrossoverType enumeration.
  • get and set mutationType : short type, chosen Mutation Type based on MutationType enumeration.
  • get and set selectionType : short type, chosen Selection Type based on SelectionType enumeration.
  • get and set size : int type, size of gen inside chromosome.
  • get and set chromosome : T* type, chromosomes inside class, used by user for initialization.
  • get and set fitness : float* type, fitness of chromosomes inside class, used by user in fitness check.
  • get bestChromosome : T* type, best chromosome after process is done, used by user as an output of the process.
  • get lastBestFitness : float type, best fitness after process is done, used by user as an output of the process.
  • get totalTime : float type, total execution time after process is done, used by user as an output of the process.
  • get lastGeneration : long type, last number of generation after process is done, used by user as an output of the process.

4. Callable method

  • void run() : to run the entire algorithm after implementation method of class is done.
  • float* generateBestFitnessHistory() : get Best Fitness in all generation after the process is done, used by user as an output of the process.
  • float* generateAverageFitnessHistory() : get Average Fitness in all generation after the process is done, used by user as an output of the process.

5. Utility

  • float randomUniform() : can be called inside or outside GPU method. Random float from 0 until 1.
  • int randomInt(int max) : can be called inside or outside GPU method. Random int from 0 until max.
  • int randomInt(int min, int max) : can be called inside or outside GPU method. Random int from min until max.
  • float randomFloat(float max) : can be called inside or outside GPU method. Random float from 0 until max.
  • float randomFloat(float min, float max) : can be called inside or outside GPU method. Random float from min until max.

6. Virtual/Abstract Method

  • virtual void doInitialization() : initialize initial values of gens of chromosomes. Must be implemented.
  • virtual void doFitnessCheck(long chromosomeAmount) : do fitness check on chromosome and store it in fitness variable. Amount of chromosome that are being calculated = chromosomeAmount variable. Must be implemented.
  • virtual void setGenChangedOption(bool* genChangedOption) : set variable genChangedOption (used to indicate if gen at certain position can be changed or not with size of genChangedOption = size of chromosome). Can be implemented (optional).
  • virtual void randomChromosome(T* newChromosome) : random full set of gen of newChromosome (size of newChromosome = size of chromosome). Can be implemented (optional).

WOA_Lib

List of things inside library can be accessed by user:

1. Constructor

  • WOA_Lib(int size) : default parameters are numberOfSearchAgent = 200, generation = 10000
  • WOA_Lib(long generation, int size, long numberOfSearchAgent)
  • ~WOA_Lib()

2. Accessor and Mutator

  • get and set generation : long type, the number of generation inside the process, process terminated if currentGeneration number has passed generation number.
  • get and set numberOfSearchAgent : int type, the amount of search agent per generation to be operated with WOA operator in every loop. See Whale Optimization Algorithm
  • get and set searchAgent : float* type, search Agents inside class, used by user for initialization.
  • get and set size : int type, size of gen inside searchAgent.
  • get and set fitness : float* type, fitness of search agents inside class, used by user in fitness check.
  • get leader : float* type, best search agent(leader) after process is done, used by user as an output of the process.
  • get lastBestFitness : float type, best fitness after process is done, used by user as an output of the process.
  • get totalTime : float type, total execution time after process is done, used by user as an output of the process.
  • get lastGeneration : long type, last number of generation after process is done, used by user as an output of the process.

3. Callable method

  • void run() : to run the entire algorithm after initialization class done.
  • float generateBestFitnessHistory()* : get Best Fitness in all generation after the process is done, used by user as an output of the process.
  • float generateAverageFitnessHistory()* : get Average Fitness in all generation after the process is done, used by user as an output of the process.

4. Utility

  • float randomUniform() : can be called inside or outside GPU method. Random float from 0 until 1.
  • int randomInt(int max) : can be called inside or outside GPU method. Random int from 0 until max.
  • int randomInt(int min, int max) : can be called inside or outside GPU method. Random int from min until max.
  • float randomFloat(float max) : can be called inside or outside GPU method. Random float from 0 until max.
  • float randomFloat(float min, float max) : can be called inside or outside GPU method. Random float from min until max.

5. Virtual/Abstract Method

  • virtual void doInitialization() : initialize initial values of gens of search agents. Must be implemented.
  • virtual void doFitnessCheck(long searchAgentAmount) : do fitness check on searchAgent and store it in fitness variable. Amount of searchAgent that are being calculated = searchAgentAmount variable. Must be implemented.
  • virtual void setGenChangedOption(bool* genChangedOption) : set variable genChangedOption (used to indicate if gen at certain position can be changed or not with size of genChangedOption = size of search agent). Can be implemented (optional).
  • virtual void randomSearchAgent(T* newSearchAgent) : random full set of gen of newSearchAgent (size of newSearchAgent = size of search agent). Can be implemented (optional).

Things to be Looked Before Using Library

  1. Maximum size of individual depends on hardware's Maximum Threads Per Block. To see your device capability, open deviceQuery on CUDA Samples Code (Example path of CUDA 9.1: C:\ProgramData\NVIDIA Corporation\CUDA Samples\v9.1\1_Utilities\deviceQuery).

  2. GA_Lib only support chromosome with type: Boolean, Char, Short, Integer, Float, Double, Long, and Long Long.

  3. WOA_Lib only support search agent with type float (no need to be initialized like GA_Lib).

  4. Virtual void that must be implemented: doInitialization, doFitnessCheck.

  5. Virtual void that can be implemented (optional): setGenChangedOption, randomChromosome.

  6. Library Constructor must be called.

  7. generation parameter must be even number.

  8. crossoverRate and mutationRate parameter must be between 0 and 1.

  9. Virtual void doInitialization must initialize the individual as many as the number of chromosomePerGeneration or numberOfSearchAgent.

  10. Virtual void doFitnessCheck must do calculation on individual's fitness as many as the number of variable chromosomeAmount or searchAgentAmount that resides in parameter.

  11. Virtual void doFitnessCheck can be implemented on GPU or CPU. For GPU Implementation, look at number 11.

  12. For GPU Implementation, user must create a new class, change the .cpp file into .cu file and item type to be CUDA C++, and call as following:

    <...>: defined by user

    <T>: change this into user's chromosome type

    User Class

    #include <userFitness.h>
void <...>::doFitnessCheck(long chromosomeAmount) {
    <T>* chromosomeTemp = this->getChromosome();
    float* fitnessTemp = this->getFitness(); 

    callFitnessCheck(getSize(), chromosomeTemp, fitnessTemp, chromosomeAmount);
};

    userFitness.cu

    __device__ float fitnessOfChromosome(<T>* chromosome, int startPoint) {
  float nilai = 0.0f;
  ..... (Calculate fitness of chromosome with index=startPoint) .....
  return nilai;
};

__global__ void fitnessCheck(int size, <T>* chromosome, float* fitness) {
  int i = blockIdx.x * blockDim.x + threadIdx.x;
  fitness[i] = fitnessOfChromosome(chromosome, i);
}

void callFitnessCheck(int size, <T>* chromosome, float* fitness, long chromosomeAmount) {
  fitnessCheck<<<1,chromosomeAmount>>>(size, chromosome, fitness);
}

  13. Virtual void setGenChangedOption must set genChangedOption variable as many as the number of chromosomePerGeneration or numberOfSearchAgent.

  14. Virtual void randomChromosome or randomSearchAgent must random gen of individual and set it to newChromosome or newSearchAgent that resides in parameter (the size is the same as size variable).

  15. No pointer address inside the library can be changed (even the parameter on virtual void), since pointer addresses need to remain inside GPU.

  16. No outside array - that's constructed by user - can be accessed inside virtual void doFitnessCheck (only if doFitnessCheck done by GPU Process). To use GPU implementation on doFitnessCheck that requires outside variable, user needs to allocate variable array inside GPU.

  17. Calling library constructor is enough to set the type of stopping criteria. If in 100.000 generation, the best Fitness doesn't change, the process terminated.

How to Use Library (Example on CLR Project C++)

The given steps is using CLR Project in Visual Studio to create a new C++ project to use the library:

  1. On the menu bar, choose File, New, Project, then choose Visual C++, CLR, CLR Empty Project. Fill the project name and location and click OK.

    Step 1

  2. On the toolbar, change the configuration project from x86 into x64.

    Step 2

  3. On the solution explorer, right click the project and choose Build Dependencies, Build Customizations. Check the box on the CUDA Build Customization Files. Click OK.

    Step 3

  4. On the solution explorer, right click the project and choose Properties. In VC++ Directories tab, add path to the header library on Include Directories and add path to the library .lib and .dll files on Library Directories.

    Step 4

  5. Still at the project properties, in Linker, Input tab, add cudart.lib; GA_Lib.lib; WOA_Lib.lib into Additional Dependencies. You can exclude the other library if you're only using one type of library. Click OK if done.

    Step 5

  6. On the solution explorer, right click the project and choose Add, Class to create a new C++ Class. Click Add to continue to next step.

    Step 6

  7. Fill the Class name field with your class name, then click Finish.

    Step 7

  8. Open the header file of created class. Give #include header to include library that you wish to use, then create a new derived class from library class (GA_Lib or WOA_Lib). Create interface for all method that you wish to use, especially must implemented abstract class (doInitialization and doFitnessCheck).

    Step 8

  9. Open the cpp file of created class, then implement all the abstract and created method from header files. Call void run to run the library process.

    Step 9

Project Examples

For easier understanding, let's start with making a new simple project to solve a given function: y = 5 + 10x -x2. The given problem will be solved using GA_Lib. The representation of chromosomes will be boolean with size = 5, as the representation of decimal number (max=32) that's created into 5 representation binary (0 or 1). The goal is to find the maximum value of x, with y act as fitness value of 1 chromosome.

Here is the code interface inside header class:

#include <GA_Lib.h>

class tryFunc : GA_Lib<bool> {
public:
	tryFunc();
	void doInitialization();
	void doFitnessCheck(long chromosomeAmount);
};

After giving an interface of derived class from GA_Lib<bool>, the next step is to implement all the methods that we created inside header file. For the constructor parameter, we will use:

  • generation = 100
  • size = 5
  • chromosomePerGeneration = 10
  • mutationRate = 0.15
  • crossoverRate = 0.35
  • crossoverType = CrossoverType::OnePointCrossover
  • mutationType = MutationType::SwapMutation
  • selectionType = SelectionType::RankSelection


For the code inside cpp file, here is the things that will be done inside all the methods:

  • Constructor: call library constructor and set all parameter, call void run, then print the best chromosome.
  • doInitialization: fill all gens of chromosomes inside class with number 1 or 0. Since pointer can't be replaced, you need to get the address of chromosome with getChromosome().
  • doFitnessCheck: fill the fitness of chromosomes inside class with y function as mentioned above. To make it easier, the implementation is done in CPU.

And here is the complete code inside cpp file:

tryFunc::tryFunc() : GA_Lib((long)100,5,10,0.15,0.35,
	CrossoverType::OnePointCrossover, MutationType::SwapMutation, SelectionType::RankSelection)
{
	run();
	bool* bestChromosome = getBestChromosome();
	printf("Best Chromosome: ");
	for (size_t i = 0; i < getSize(); i++) {
		printf("%i ", bestChromosome[i]);
	}
	printf("\n");
}

void tryFunc::doInitialization() {
	bool* chromosomeTemp = getChromosome();
	for (int i = 0; i < getChromosomePerGeneration(); i++)
	{
		for (int j = 0; j < getSize(); j++) {
			chromosomeTemp[i*getSize()+j] = randomInt(1);
		}
	}
	setChromosome(chromosomeTemp);
}

void tryFunc::doFitnessCheck(long chromosomeAmount) {
	bool* chromosomeTemp = getChromosome();
	float* fitnessTemp = getFitness();
	for (int i = 0; i < chromosomeAmount; i++)
	{
		float score = 0.0f;
		for (int j = 0; j < 5; j++)
		{
			score += (chromosomeTemp[i*getSize() + j] == 0 ? 0 : powf(2,j));
		}
		fitnessTemp[i] = 5 + 10 * score - (score*score);
	}
}

After the class has been filled in with implementation code, the process will run in main project by including class header and calls tryFunc try. And here is the result:

Operation Finished..
Total Execution Time: 0.263000 s
Operation finished in generation 100...
Best Fitness in last generation: 30.000000
Best Chromosome: 1 0 1 0 0

There are other provided examples of GA_Lib and WOA_Lib for Sudoku and TSP problems. For project examples, see Project Examples . For CPU implementation code inside the examples, choose the project that have keyword "CPU" in its name.