K-Coloring Problem Genetic Algorithm

K-Coloring Problem

The K-Coloring problem is a well-known computer science problem. It belongs to the NP problem class, specifically to the NP-Complete subclass. The aim of this algorithm is to find the minimum number of colors in order to color an undirected graph, without assigning the same color to adjacent vertices. Due to the complexity of this problem, the algorithm won’t find the best solution, but an optimal one in an acceptable amount of time.

How to run

In order to correctly run the genetic algorithm, there are some rules that must be respectes:

• The values of the variable nthread and its counterpart in the environment declaration (the cloud variable) must be equal.
• The edges matrix and its counterpart in the fitness function must be equal.
• The value of tournamentSize must be less than dimension’s one.
• The value of nThread, dimension, individualLength, tournamentSize, resultSize and genToStop must be greater than 0.
• Each other variable must not be changed.

Functions

The program is composed by five principal functions:

• Initialization Function
• Fitness Function
• Selection Function
• Crossover Function
• Mutation Function

Initialization Function

The initialization function initialize the population with random values between 0 and individualLength. The Fly code is the following:

func initPopulation(){
	var newPop = Integer[dimension][individualLength]
	population= newPop
	var rand = [type="random"]
	
	for i in [0:dimension]{
		for j in [0:individualLength]{
			var value = 0
			value = rand.nextInt(individualLength)
			
			if(value < 0){
				value = value * -1
			}
			
			population[i][j]= value
		}
	}
}

Fitness Function

The fitness function evaluates each individual in population or in newIndividuals. The evaluation of an individual is the number of conflicts in the colouration pattern of the vertices. The function in written in JavaScript. The code is the following:

 native<<<
 var edges = [[0, 1, 0, 1, 0], [1, 0, 1, 0, 1], [0, 1, 0, 0, 0], [1, 0, 0, 0, 1], [0, 1, 0, 1, 0]]
        
console.log(event.data[0])	
var resultJSON = "[" + submatrixIndex + ", " + __populationMatrix_rows + ", "
	
for(var __i = 0; __i < __populationMatrix_rows; __i++){
	var fitnessValue = 0
	for(var __j = 0; __j < __populationMatrix_cols; __j++){
		var currentColor = populationMatrix[__i][__j]
		for(var __k = 0; __k < __populationMatrix_cols; __k++){
			var edgeValue = edges[__j][__k]
                	var edgeColor = populationMatrix[__i][__k]
                
               		if(__k != __j && edgeValue == 1 && currentColor == edgeColor){
                    		fitnessValue += 1
                	}
		}
	}
	resultJSON += "" + (fitnessValue/2)
		
	if(__i >= 0 && __i < __populationMatrix_rows - 1){
    		resultJSON += ", "
    	}
}
	
	resultJSON += "]";
	console.log("Result: " + resultJSON)
	__data = await __sqs.getQueueUrl({ QueueName: "ch-'${id}'"}).promise();
		
	__params = {
		MessageBody : JSON.stringify(resultJSON),
		QueueUrl : __data.QueueUrl
	};
		
	__data = await __sqs.sendMessage(__params).promise();
	__data = await __sqs.getQueueUrl({ QueueName: "termination-'${function}'-'${id}'"}).promise();
>>>

This funcition is made to evaluate a portion of individuals in a serverless environment. For this reason, results are formatted in a Json string, containing also the number of evaluated individuals and the submatrixIndex number. Results are sent to the client over a channel, ordered by submatrixIndex number and assigned to each evaluated individual.

Selection Function

The selection function selects the individuals which can access the crossover phase. The Tournament Selection creates torunaments with tournamentSize different individuals randomly picked from the population and select the best individual, the one with the best fitness. The winner of the tournament is inserted in the champions pool, which is used for the crossover. The Fly code is the following:

func tournamentSelection(){
	var selectedIndividual = -1
	var rand = [type="random"]
	
	var tournament = Integer[tournamentSize]
	
	for j in [0:tournamentSize]{
		var element = 0
		element = rand.nextInt(dimension)
		
		if(element < 0){
			element = element * -1
		}
		
		tournament[j] = element
		
		for i in [0:tournamentSize]{
			if(i != j){
				if(tournament[i] == tournament[j]){
					tournament[j] = -1	
				}
			}
		}
		
		if(tournament[j] == -1){
			j = j - 1
		}
	}
	
	var best = 0
	best = tournament[0]
	
	for j in [1:tournamentSize]{
		if(populationFitness[j] < populationFitness[best]){
			best = tournament[j]
		}
	}
	
	selectedIndividual = best
	return selectedIndividual
}

Crossover Function

The crossover function combines the genes of two individuals in order to generate one or more new individuals. The One Point Crossover cuts parent1 and parent2 in two parts, using a randomly generated crossoverPoint. Every execution of this function generates two new individuals, child1 and child2, by swapping the cut parts. The Fly code is the following:

func onePointCrossover(){
	var rand = [type="random"]
	var crossoverPoint = 0
	crossoverPoint = rand.nextInt(individualLength - 1)
	
	while(crossoverPoint == 0){
		crossoverPoint = rand.nextInt(individualLength - 1)
	}
	
	if(crossoverPoint < 0){
		crossoverPoint = crossoverPoint * -1
	}
	
	var p1 = Integer[individualLength]
	var p2 = Integer[individualLength]
	
	for i in [0:individualLength]{
		p1[i] = population[parent1][i]
	}
	
	for i in [0:individualLength]{
		p2[i] = population[parent2][i]
	}
	
	var last2= Integer[individualLength - crossoverPoint]
	var n = 0
	for i in [crossoverPoint:individualLength]{ //Swap 1
		last2[n] = p2[i]
		n++
		p2[i] = p1[i]
	}
	
	var first1 = Integer[crossoverPoint]
	n = 0
	for i in [0:crossoverPoint]{ //Swap 2
		first1[n] = p1[i]
		n++
		p1[i] = p2[i]
	}
	
	n = 0
	var m = 0
	for i in [0:crossoverPoint]{
		if(i < crossoverPoint){
			p2[i] = first1[n]
			n++
		}
		else{
			p2[i] = last2[m]
			m++
		}
	}
	
	for i in [0:individualLength]{
		child1[i] = p1[i]
		child2[i] = p2[i]
	}
}

Mutation Function

The mutation function randomly changes values in the gene pool of an individual. The Gaussian Mutation is completely based on the probability, in fact it uses the mutationChance variable to decide if a determined gene will be changed or not. Moreover, the access to the mutation process is determined by the value of another randomly generated variable, the mutationProbability. The Fly code is the following:

func gaussianMutation(){
	var rand = [type="random"]
	
	for i in [0:individualLength]{
		var mutationChance = 0
		mutationChance = rand.nextInt(2)
		
		if(mutationChance < 0){
			mutationChance = mutationChance * -1
		}
		
		if(mutationChance > 0){
			var mutationValue = 0
			mutationValue = rand.nextInt(individualLength)
			
			if(mutationValue < 0){
				mutationValue = mutationValue * -1
			}
				toMutate[i] = mutationValue
		}
	} 
}