-
Notifications
You must be signed in to change notification settings - Fork 33
Tutorial
Before we start our tutorial, we must have a runnable environment installed. Please follow our README to prepare the environment.
We can use pip3 install git+git://github.com/PyOCL/OpenCLGA.git command to install OpenCLGA. Once installed, we can download the example code from our repository to test it.
It is important to define the problem before solving a problem. According to Artificial Intelligence book, the common procedure to define a problem for Genetic Algorithm is:
- Specify the problem, define constraints and optimum criteria.
- Represent the problem domain as a chromosome.
- Define a fitness function to evaluate the chromosome's performance.
- Construct the genetic operators.
- Run the GA and tune its parameters.
In this section, we will cover 1, 2, and 3. Item 4 and 5 will be left at next section.
The problem in this tutorial is a typical scheduling problem, which is also the same example at Artificial Intelligence book. A power station has 7 power generation units. The power generated by this power station should be continuous which means 24x7 running, even if we stop some units for maintenance.
The output of each units are 20, 15, 35, 40, 15, 15, and 10. The maximum power load of 4 seasons are: 80, 90, 65 and 70 MW. For unit 1 and unit 2, we need 2 seasons for maintenance and others are 1 season. Every units should be maintained once a year. During the maintenance, the power reserve must be sufficient which means all power output must cover power load of every season.
The objective of this problem is to find a maintenance schedule which gives us the maximum power reserve. The constraints of this problem are:
- The maintenance must be at adjacent season for unit 1 and unit 2.
- The power reserve must be greater than or equal to 0.
The minimum power reserve is the best way to evaluate a maintenance schedule. For example, if we have power reserve for each seasons: 20, 10, 30, and 5 MW, the minimum power reserve is 5 MW at winter.
According to objective section, we need a maintenance schedule for these 7 units, that can be a chromosome. The chromosome can be designed as maintaining season of these 7 units.
The unit 1 and 2 have 4 candidates:
- season 1 and 2 (q12)
- season 2 and 3 (q23)
- season 3 and 4 (q34)
- season 4 and 1 (q41)
The unit 3, 4, 5, 6, and 7 have 4 candidates:
- season 1 (q1)
- season 2 (q2)
- season 3 (q3)
- season 4 (q4)
A chromosome may look like this: [unit 1, unit 2, unit 3, unit 4, unit 5, unit 6, unit 7] and an example may be: [q12, q12, q1, q1, q1, q1, q1].
The fitness function is an equation to calculate the minimum power reserve of a schedule. It may be:
season 1 = Sum(power generated by units running at q1) - 80
season 2 = Sum(power generated by units running at q2) - 90
season 3 = Sum(power generated by units running at q3) - 65
season 4 = Sum(power generated by units running at q4) - 70
fitness = min(season 1, season 2, season 3, season 4)
An app using OpenCLGA should have Python and OpenCL.
- Python: this part describes chromosome structure and gets the result.
- OpenCL: this part implements the fitness function.
Python - power.py
There are two functions in this file: show_generation_info and run. The show_generation_info prints the current best fitness value to screen, and run executes OpenCLGA. Since show_generation_info is too simple, we will focus on run function at this section.
We need to prepare the sample chromosome for OpenCLGA, like the below. As previous design, there are two types power generators: type1 and type2. The unit 1 and 2 are type1, and others are type2.
type1 = ['q12', 'q23', 'q34', 'q41']
type2 = ['q1', 'q2', 'q3', 'q4']
sample = SimpleChromosome([SimpleGene('q12', type1, 'unit-1'),
SimpleGene('q12', type1, 'unit-2'),
SimpleGene('q1', type2, 'unit-3'),
SimpleGene('q1', type2, 'unit-4'),
SimpleGene('q1', type2, 'unit-5'),
SimpleGene('q1', type2, 'unit-6'),
SimpleGene('q1', type2, 'unit-7')])We use file open to read our fitness function into memory:
self_path = os.path.dirname(os.path.abspath(__file__))
f = open(os.path.join(self_path, 'power.cl'), 'r')
fstr = ''.join(f.readlines())
f.close()And then, we initialize OpenCLGA:
import threading
evt = threading.Event()
evt.clear()
def state_changed(state):
if 'stopped' == state:
evt.set()
ga_cl = OpenCLGA({'sample_chromosome': sample,
'termination': {
'type': 'count',
'count': generations
},
'population': num_chromosomes,
'fitness_kernel_str': fstr,
'fitness_func': 'power_station_fitness',
'opt_for_max': 'max',
'debug': True,
'generation_callback': show_generation_info},
action_callbacks = {'state' : state_changed})
ga_cl.prepare()There is a tricky part here. We use a thread event for asynchronous execution because OpenCLGA will fork a thread to run the code. A state change callback function is needed to know the state change. All states can be found here. The argument list is:
- sample_chromosome: it is a chromosome sample.
- termination: it is the termination criteria. There are two types: count and time. If we want to run OpenCLGA in N generations, we should use count: N. If we want to run OpenCLGA in X seconds, we can use time: X.
- population: it is the population size for a generation.
- fitness_kernel_str: it is the fitness source code.
- fitness_func: it is the entry function name of fitness function.
- opt_for_max: it is the optimization direction. There are two values here: min and max. In this case, we want to maximum the minimum power reserve.
- debug: it is a flag to show debug message or not.
- generation_callback: it is the callback function for performance of each generation.
It's almost ready to run the code:
prob_mutate = 0.05
prob_cross = 0.8
ga_cl.run(prob_mutate, prob_cross)
evt.wait()We use 5% mutation ratio and 80% crossover ratio to run the GA and wait for the result.
Once the result back, we draw the statistic line charts and output the best schedule to console:
utils.plot_ga_result(ga_cl.get_statistics())
print('run took', ga_cl.elapsed_time, 'seconds')
best_chromosome, best_fitness, best_info = ga_cl.get_the_best()
print('Best Fitness: %f'%(best_fitness))
print('1 ~ 7 units are maintained at: ' + ', '.join(str(g.dna) for g in best_info.genes))OpenCL - power.cl
The first part of power.cl are power generation function for 2 types of units:
void generate_powers_type1(int* quarters, int value, int power) {
// for type 1 power station, it uses 2 quarters for maintainence.
// no power generates if it is at quarter 1, 2 or quarter 4, 1
quarters[0] += (value == 3 || value == 0 ? 0 : power);
// no power generates if it is at quarter 1, 2 or quarter 2, 3
quarters[1] += (value == 0 || value == 1 ? 0 : power);
// no power generates if it is at quarter 2, 3 or quarter 3, 4
quarters[2] += (value == 1 || value == 2 ? 0 : power);
// no power generates if it is at quarter 3, 4 or quarter 4, 1
quarters[3] += (value == 2 || value == 3 ? 0 : power);
}
void generate_powers_type2(int* quarters, int value, int power) {
// for type 2 power station, it uses 1 quarters for maintainence.
// no power generates if it is at quarter 1
quarters[0] += (value == 0 ? 0 : power);
// no power generates if it is at quarter 2
quarters[1] += (value == 1 ? 0 : power);
// no power generates if it is at quarter 3
quarters[2] += (value == 2 ? 0 : power);
// no power generates if it is at quarter 4
quarters[3] += (value == 3 ? 0 : power);
}The parameters of these two functions are:
- quarters: it is an array of generated power at 4 seasons.
- value: it is the maintaining schedule of this power unit. For type 1, 0 means q12, 1 means q23, 2 means q34, and 3 means q41. For type1, 0 means q1, 1 means q2, 2 means q3, and 3 means q4.
- power: it is the power output of a power unit.
We can calculate the power reserve for 4 seasons with these two functions:
// The power generated by all units.
int CAPACITIES[] = {20, 15, 34, 50, 15, 15, 10};
// The maximum load of each quarter
int LOADS[] = {-80, -90, -65, -70};
// calculate the power generation by unit 1 ~ 7 at each quarters.
generate_powers_type1(LOADS, chromosome->genes[0], CAPACITIES[0]);
generate_powers_type1(LOADS, chromosome->genes[1], CAPACITIES[1]);
generate_powers_type2(LOADS, chromosome->genes[2], CAPACITIES[2]);
generate_powers_type2(LOADS, chromosome->genes[3], CAPACITIES[3]);
generate_powers_type2(LOADS, chromosome->genes[4], CAPACITIES[4]);
generate_powers_type2(LOADS, chromosome->genes[5], CAPACITIES[5]);
generate_powers_type2(LOADS, chromosome->genes[6], CAPACITIES[6]);Then, let's calculate the minimum power reserve for this schedule:
*fitnesses = LOADS[0] < LOADS[1] ? LOADS[0] : LOADS[1];
if (LOADS[2] < LOADS[3] && LOADS[2] < *fitnesses) {
*fitnesses = LOADS[2];
} else if (LOADS[3] < *fitnesses) {
*fitnesses = LOADS[3];
}
if (*fitnesses < 0) {
*fitnesses = 0;
}The final program can be found at our examples