CODEWITHSUNDEEP
pythongenetic-algorithm
user10683480
user10683480

Reputation:

How to select parent using roulette wheel?

I'm trying to implement a genetic algorithm for solving the Travelling Salesman Problem (TSP).

I have 2 classes, which are City and Fitness.

I have done the code for initialization. 

class City:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distance(self, city):
        xDis = abs(self.x - city.x)
        yDis = abs(self.y - city.y)
        distance = np.sqrt((xDis ** 2) + (yDis ** 2))
        return distance

    def __repr__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"

class Fitness:
    def __init__(self, route):
        self.route = route
        self.distance = None
        self.fitness = None

    def routeDistance(self):
        if self.distance == None:
            pathDistance = 0.0
            for i in range(0, len(self.route)):
                fromCity = self.route[i]
                toCity = None
                if i+1 < len(self.route):
                    toCity = self.route[i+1]
                else:
                    toCity = self.route[0]
                pathDistance += fromCity.distance(toCity)
            self.distance = pathDistance
        return self.distance

    def routeFitness(self):
        if self.fitness == None:
            self.fitness = 1 / float(self.routeDistance())
        return self.fitness


def selection(population, size=None):

    if size== None:
        size= len(population)

    matingPool = []

    fitnessResults = {}
    for i in range(0, size):
        fitnessResults[i] = Fitness(population[i]).routeFitness()
        matingPool.append(random.choice(population))

    return matingPool

The code above just randomly selects a parent in the selection method.

My question is: How to code to select a parent using roulette wheels?

Upvotes: 2

Views: 1191

Answers (2)

guroosh
guroosh

Reputation: 652

Read this

So basically, the higher a fitness value, the higher are its chances to be chosen. But that is when high fitness value means a high fitness. But in TSP a lower value of fitness is better so to implement this, we need to implement the concept where probability is indirectly proportional to the fitness value.

Here is something I had implemented in python with some changes

def choose_parent_using_RWS(genes, S):
    P = random.uniform(0, S)
    for x in genes:
        P += get_fitness_value(x)
        if P > S:
            return x
    return genes[-1]

where S is the sum of the inverse of the fitness values of the current population (i.e, 1/f1 + 1/f2 + 1/f3 + ...)

and

get_fitness_value(x) returns the inverse of the distance, just like your routeFitness() function

TeeHee

Upvotes: 0

Reveille
Reveille

Reputation: 4629

You could try this [1, 2]:

from numpy.random import choice

def selection(population, size=None):

    if size== None:
        size= len(population)

    fitnessResults = []
    for i in range(0, size):
        fitnessResults.append(Fitness(population[i]).routeFitness())

    sum_fitness = sum(fitnessResults)
    probability_lst = [f/sum_fitness for f in fitnessResults]

    matingPool = choice(population, size=size, p=probability_lst)

    return matingPool

Upvotes: 1

Related Questions