Как выбрать родителя с помощью колеса рулетки?

Question

Я пытаюсь реализовать генетический алгоритм для решения задачи коммивояжера (TSP).

У меня есть 2 класса: Город и Фитнес.

Я сделал код для инициализации.

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

Приведенный выше код просто случайным образом выбирает родителя в методе выбора.

Мой вопрос: как кодировать, чтобы выбрать родителя с помощью колес рулетки?

Answer 1

Вы можете попробовать это [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

Answer 2

Читать это

Таким образом, в принципе, чем выше значение пригодности, тем выше его шансы на выбор. Но именно тогда высокая ценность пригодности означает высокую пригодность. Но в TSP более низкое значение пригодности лучше, поэтому для его реализации нам необходимо реализовать концепцию, в которой вероятность косвенно пропорциональна значению пригодности.

Вот что я реализовал в python с некоторыми изменениями

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]

где S - сумма обратных значений пригодности текущего населения (т. Е. 1 / f1 + 1 / f2 + 1 / f3 + ...)

и

get_fitness_value (x) возвращает значение, обратное расстоянию, так же, как ваша функция routeFitness ()

TeeHee