حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک | راهنمای جامع حل مسئله در پایتون در ۷ گام

از کارمندان برج‌های مراقبت، معماران ساختمان‌ها و پروژه‌های بزرگ بیمارستانی و حتی ساختمان‌های مسکونی تا شهرداری‌ها و حتی شرکت‌های ثبت‌احوال به‌نوعی از مسئله فروشنده دوره گرد برای مدیریت روال کار خود، استفاده می‌کنند. باور نمی‌کنید؟! اشکال ندارد. با توضیحات بنده باور خواهید کرد که مسئله فروشنده دوره گرد، بسیاری از امور مسیریابی و برنامه‌ریزی ادارات و سازه‌ها را مدیریت می‌کند.

بالفرض شهرداری‌ها، ساعت‌ها برای پخش ماشین‌های جمع‌آوری زباله برنامه‌ریزی می‌کنند که چگونه بتوانند در کمترین زمان و با حداقل هزینه به پاک‌سازی سطح شهر بپردازند یا اداره‌های ثبت‌احوال و شهرک‌های آزمایش، برنامه‌ریزی می‌کنند که چگونه با مدیریت امور، ترافیک مراجعین خود را به صفر برسانند. پس بیایید از قافله عقب نمانیم و ما هم الگوریتم مناسب خود را برای جست‌وجوی بهترین مسیر و بهینه‌ترین حالت ممکن بیابیم.

فعلاً در آموزش فروشنده دوره گرد با الگوریتم ژنتیک، مطالعاتمان را با شما به اشتراک گذاشته و بررسی می‌کنیم که نحوه عملکرد آن به چه شکل است. پیاده‌سازی‌ها در محیط برنامه‌نویسی پایتون انجام می‌گردد. در ادامه، گام‌های آموزش را دنبال کنید تا ببینید که چگونه می‌توان با چند کد ساده، از پیچیدگی امور روزمره و دست‌وپا گیر روزانه کم کرد.

طرح مسئله فروشنده دوره گرد

اگر از همراهان همیشگی ما هستید؛ به خوبی می‌دانید که قبلاً هم در مورد الگوریتم ژنتیک و هم در مورد مسئله فروشنده دوره گرد و الگوریتم‌های حل این مسئله به‌طور مفصل بحث کرده‌ایم اما اگر به‌تازگی به جمع ما پیوسته‌اید؛ نگران نباشید که ما برای یادآوری، به تشریح کامل مسئله خواهیم پرداخت.

درواقع، با توجه به فهرستی از شهرها که قبلاً توسط آقا یا خانم دوره گرد تهیه‌شده است و با توجه به فواصل بین هر جفت شهر، باید تعیین کنیم که کوتاه‌ترین مسیر ممکن برای بازدید از هر شهر و بازگشت به شهر مبدأ یا شهری که خانه و خانواده در آنجا منتظر هستند؛ کدام است؟ به‌عبارت‌دیگر، ما می‌خواهیم فروشنده ما خیلی از خانواده‌اش دور نماند. سریع و با حداقل هزینه، محصولاتش را در شهرهای تعیین‌شده به فروش رسانده و به خانه برگردد پس با استفاده از الگوریتم ژنتیک، مسیر بهینه را برای او خواهیم یافت و راهنمایی‌اش خواهیم کرد.

دستاوردهای مسئله فروشنده دوره گرد

با توجه به‌صورت مسئله و توضیحات بالا، دو قانون مهم در مورد مسئله دوره گرد وجود دارد که باید رعایت شود. در ادامه آن دو قانون بیان‌شده است.

1. هر شهر باید دقیقاً یک بار بازدید شود و به‌هیچ‌عنوان، امکان بازگشت به شهر قبلی وجود ندارد.
2. فروشنده حتماً و حتماً باید به شهر شروع بازگردد. بنابراین مسافت کل باید بر اساس این قانون، محاسبه شود.

اصطلاحات رایج در الگوریتم ژنتیک برای TSP

برای درک بهتر مراحل، در ابتدا به تعریف چند اصطلاح ساده از الگوریتم ژنتیک که در قالب TSP نوشته‌شده‌اند؛ می‌پردازیم تا علاوه بر تعیین چارچوب حل مسئله، هوای همراهان مبتدی را هم داشته باشیم و اجازه ندهیم که دچار سردرگمی شوند و از مطالعه این مقاله لذت ببرند.

• ژن: به هرکدام از شهرها یک ژن یا فرد گفته می‌شود که با مختصات (x,y) نشان داده خواهد شد.
• کروموزوم: یک مسیر واحد از یک شهر به شهر دیگر، تحت مختصات (x,y)، کروموزوم نامیده می‌شود.
• جمعیت: مجموعه‌ای از مسیرهای ممکن به‌عنوان‌مثال، مجموعه افراد، تحت عنوان جمعیت شناخته خواهد شد.
• والدین: دو مسیری که برای ایجاد یک مسیر جدید ترکیب‌شده و در اصطلاح ژنتیک، عمل آمیزش را انجام می‌دهند.
• تناسب یا فیتنس: تابعی که به ما می‌گوید هرکدام از مسیرها تا چه اندازه بهینه هستند. در مسئله فروشنده دوره گرد، کوتاه‌ترین مسیر، همان مسیر بهینه خواهد بود.
• جهش: راهی برای معرفی تنوع در جمعیت! تعویض تصادفی دو شهر در یک مسیر، جهش نامیده می‌شود.
• نخبه‌گرایی: روشی که برای انتقال بهترین افراد به نسل بعدی، استفاده می‌شود؛ نخبه‌گرایی نام دارد.

رویکرد حل مسئله TSP با الگوریتم ژنتیک

الگوریتم ژنتیک در طی ۷ گام، برای مسئله فروشنده دوره گرد پاسخ بهینه معرفی خواهد کرد که عبارت‌اند از:

1.  ایجاد جمعیت
2. ایجاد تابع برازندگی
3. تعیین فضای ترکیب
4. تولید اولین نژاد جمعیت
5. انجام عملیات تولیدمثل
6. پیاده‌سازی عملیات جهش
7. تکرار الگوریتم

به نمودار خلاصه‌شده زیر، توجه کنید تا به یک ایده کلی از رویکرد حل مسئله توسط الگوریتم ژنتیک، برسید و در ادامه، برای تشریح گام‌های حل مسئله، با ما همراه باشید. در لینک زیر پکیج حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک در پایتون  برای شما عزیزان ارائه داده‌ایم. برای دسترسی به لینک زیر مراجعه کنید.

• آموزش نحوه پیاده سازی حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک در پایتون — کلیک کنید.

ساخت یک الگوریتم ژنتیک ساده

قبل از شروع حل مسئله، ابتدا باید الگوریتم خودمان را بسازیم. ما برای راحتی کار، پکیج‌های آماده زیر را به شما پیشنهاد می‌کنیم.

import numpy as np, random, operator, pandas as pd, matplotlib.pyplot as plt

در ابتدا برای شروع، به دو کلاس نیاز داریم که اولی کلاس شهر است. این کلاس، به ما امکان می‌دهد که شهرهای خود را با مختصات (x,y) ایجاد کرده و به‌راحتی مدیریت کنیم. در کلاس City ایجادشده توسط تکه کد زیر، محاسبه فاصله با استفاده از قضیه فیثاغورث انجام‌شده و برای مدیریت خروجی شهرها از تابع Repr استفاده می‌کنیم.

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 = 0
        self.fitness= 0.0
    
    def routeDistance(self):
        if self.distance ==0:
            pathDistance = 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 == 0:
            self.fitness = 1 / float(self.routeDistance())
        return self.fitness

۱- گام اول: ایجاد جمعیت

در مرحله اول مسئله فروشنده دوره گرد با الگوریتم ژنتیک، نسل اول یا همان جمعیت اولیه تولید می‌شود. به این معنا که، ما یک تابع خواهیم ساخت که مسیرهایی طبق قوانین مسئله، تولید کند. در نظر داشته باشید که حتما باید برای ایجاد ژن، به طور تصادفی ترتیب بازدید از هر شهر را انتخاب کنیم. به تکه کد زیر توجه کنید.

def createRoute(cityList):
    route = random.sample(cityList, len(cityList))
    return route

تکه کد بالا، یک فرد را تولید می‌کند. درحالی‌که ما به یک جمعیت کامل نیاز داریم و یک فرد به تنهایی، مشکل ما را حل نمی‌کند پس عزیزان، بیایید از تکه کد زیر، برای ایجاد جمعیت کامل و رسیدن به تعداد مطلوب مسیرهایی که برای جمعیت خود، نیاز داریم؛ استفاده کنیم. البته در نظر داشته باشید که ما فقط باید از این توابع برای ایجاد جمعیت اولیه استفاده کنیم. نسل‌های بعدی از طریق اصلاح نژاد و جهش تولید خواهند شد.

def initialPopulation(popSize, cityList):
    population = []

    for i in range(0, popSize):
        population.append(createRoute(cityList))
    return population

def rankRoutes(population):
    fitnessResults = {}
    for i in range(0,len(population)):
        fitnessResults[i] = Fitness(population[i]).routeFitness()
    return sorted(fitnessResults.items(), key = operator.itemgetter(1), reverse = True)

def selection(popRanked, eliteSize):
    selectionResults = []
    df = pd.DataFrame(np.array(popRanked), columns=["Index","Fitness"])
    df['cum_sum'] = df.Fitness.cumsum()
    df['cum_perc'] = 100*df.cum_sum/df.Fitness.sum()
    
    for i in range(0, eliteSize):
        selectionResults.append(popRanked[i][0])
    for i in range(0, len(popRanked) - eliteSize):
        pick = 100*random.random()
        for i in range(0, len(popRanked)):
            if pick <= df.iat[i,3]:
                selectionResults.append(popRanked[i][0])
                break
    return selectionResults

def matingPool(population, selectionResults):
    matingpool = []
    for i in range(0, len(selectionResults)):
        index = selectionResults[i]
        matingpool.append(population[index])
    return matingpool

def breed(parent1, parent2):
    child = []
    childP1 = []
    childP2 = []
    
    geneA = int(random.random() * len(parent1))
    geneB = int(random.random() * len(parent1))
    
    startGene = min(geneA, geneB)
    endGene = max(geneA, geneB)

    for i in range(startGene, endGene):
        childP1.append(parent1[i])
        
    childP2 = [item for item in parent2 if item not in childP1]

    child = childP1 + childP2
    return child

عزیزان من، اگر بخواهیم برای ایجاد جمعیت فرزندان، تکه کد بالا را تعمیم دهیم؛ می‌توانیم از نخبه‌گرایی برای حفظ بهترین مسیرها از جمعیت فعلی استفاده کرده و سپس درنهایت، از تابع Breed برای پر کردن بقیه نسل بعدی استفاده کنیم. به کدهای زیر توجه کنید.

def breedPopulation(matingpool, eliteSize):
    children = []
    length = len(matingpool) - eliteSize
    pool = random.sample(matingpool, len(matingpool))

    for i in range(0,eliteSize):
        children.append(matingpool[i])
    
    for i in range(0, length):
        child = breed(pool[i], pool[len(matingpool)-i-1])
        children.append(child)
    return children

۶- گام ششم: پیاده سازی عملیات جهش

در گام ششم از فروشنده دوره گرد با الگوریتم ژنتیک، عملیات جهش را که یکی از اصلی‌ترین عملیات انجام‌شده در الگوریتم ژنتیک است را بررسی می‌کنیم. حالا چرا گفتیم عملیات جهش در GA از عملیات‌های مهم و اساسی به شمار می‌آید؟! به این دلیل که اولاً با معرفی مسیرهای جدید به ما این امکان را می‌دهد که سایر بخش‌های فضای راه‌حل را کشف کنیم. ثانیاً به جلوگیری از همگرایی محلی کمک می‌کند. به‌بیان‌دیگر می‌توان گفت که عملیات جهش، نقش آچارفرانسه در داخل یک جعبه‌ابزار را ایفا می‌کند.

در مورد مسئله فروشنده دوره گرد، ما از جهش Swap استفاده خواهیم کرد. به این معنا که با احتمال کم مشخص‌شده، دو شهر در مسیر ما جای خود را عوض می‌کنند. ما این کار را برای یک فرد در تابع جهش خود انجام خواهیم داد. به کدهای زیر توجه کنید تا بیشتر متوجه شوید.

def mutate(individual, mutationRate):
    for swapped in range(len(individual)):
        if(random.random() < mutationRate):
            swapWith = int(random.random() * len(individual))
            
            city1 = individual[swapped]
            city2 = individual[swapWith]
            
            individual[swapped] = city2
            individual[swapWith] = city1
    return individual

def mutatePopulation(population, mutationRate):
    mutatedPop = []
    
    for ind in range(0, len(population)):
        mutatedInd = mutate(population[ind], mutationRate)
        mutatedPop.append(mutatedInd)
    return mutatedPop

def nextGeneration(currentGen, eliteSize, mutationRate):
    popRanked = rankRoutes(currentGen)
    selectionResults = selection(popRanked, eliteSize)
    matingpool = matingPool(currentGen, selectionResults)
    children = breedPopulation(matingpool, eliteSize)
    nextGeneration = mutatePopulation(children, mutationRate)
    return nextGeneration

کلام آخر در مورد فروشنده دوره گرد با الگوریتم ژنتیک

بیایید آنچه گفته شد را به‌اتفاق مرور کنیم. طبق توضیحاتی که بیان گردید؛ برای حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک، اولاً جمعیت اولیه را ایجاد می‌کنیم. سپس می‌توانیم به تعداد نسل‌هایی که می‌خواهیم حلقه‌زده؛ بهترین مسیر یا میزان پیشرفت جمعیت تولیدشده را بر اساس معیار برازندگی ببینیم و نکته مهم این‌که، نیاز است این عملیات را تا رسیدن به بهینه‌ترین حالت ممکن، تکرار کنیم.

دوستان عزیز، باورتان می‌شد مسئله فروشنده دوره گرد با الگوریتم ژنتیک، به این آسانی حل شود؟ اگر جوابتان به این سؤال “نه” است؛ باید به شما بگویم که حضور شما، گرمای وجود ما است و به ما این انگیزه را می‌دهد که به دنبال راه‌حل ساده برای مشکلات پیچیده باشیم و همواره سعی کنیم که فرآیند آموزش را هرچه شیرین‌تر از قبل در اختیارتان بگذاریم. منتظر نظرات و پیشنهادات شما هستیم.

سورس کد حل مسئله فروشنده دوره گرد با الگوریتم گرگ خاکستری در پایتون

سورس کد حل مسئله فروشنده دوره گرد با الگوریتم گرگ خاکستری در پایتون

کلیک کنید