الگوریتم تکاملی تفاضلی (Differential Evolution) — راهنمای کامل و کاربردی

الگوریتم تکاملی تفاضلی یا الگوریتم DE یک الگوریتم بهینه سازی است که اولین بار در سال ۱۹۹۵ توسط Rainer Storn و Kenneth Price معرفی شد. این محققان در مقاله ای تحت عنوان Differential Evolution a Practical Approach to Global Optimization نشان دادند که این الگوریتم توانایی خوبی در بهینه سازی توابع غیرخطی مشتق ناپذیر دارد که به عنوان روشی قدرتمند و سریع برای مسائل بهینه سازی در فضاهای پیوسته معرفی شده است.

معرفی الگوریتم تکاملی تفاضلی

الگوریتم DE جهت غلبه بر عیب اصلی الگوریتم ژنتیک، یعنی نبود جستجوی محلی در این الگوریتم ارائه شده است، تفاوت اصلی بین الگوریتم‌های ژنتیک و الگوریتم DE در عملگر انتخاب Selection Operators است. در عملگر انتخاب الگوریتم GA ،شانس انتخاب یک جواب به عنوان یکی از والدین وابسته به مقدار شایستگی آن می‌باشد، اما در الگوریتم DE همه جواب‌ها دارای شانس مساوی جهت انتخاب شدن می‌باشند. یعنی شانس انتخاب شدن، وابسته به مقدار شایستگی آنها نمی‌باشد، پس از این که یک جواب جدید با استفاده از یک عملگر جهش mutation و عملگر crossover تولید شد، جواب جدید با مقدار قبلی مقایسه می‌شود و در صورت بهتر بودن جایگزین می‌گردد.

در الگوریتم تکاملی تفاضلی بر خلاف دیگر الگورتیم‌ها که اول عملگر crossover و سپس عملگر mutation انجام می‌شود به گونه‌ای که ابتدا عملگر جهش اعمال شده و سپس عملگر crossover اعمال می‌شود تا بدین وسیله نسل جدید ایجاد گردد. برای اعمال عملگر mutation از توزیع خاصی استفاده نمی‌شود بلکه طول گام جهش برابر با مقدار از فاصله میان اعضای فعلی تعیین می‌شود.

مراحل اجرای الگوریتم تکاملی تفاضلی

الگوریتم DE شامل چهار مرحله اصلی است:

۱- مقداردهی اولیه (Initialization)

ابتدا یک جمعیت تصادفی از راه‌حل‌ها در فضای جستجو تولید می‌شود. هر راه‌حل یک بردار با ابعاد برابر با تعداد متغیرهای مسئله است. برای تولید جمعیت اولیه معمولاً از توزیع یکنواخت استفاده می‌شود تا اعضای جمعیت کاملاً به طور یکسان در فضا پخش شده و در هر مرحله از الگوریتم DE این اعضا به یکدیگر نزدیک می‌شوند و این همگرایی منجر به رسیدن به جواب بهینه خواهد شد همچنین باید توجه داشت که تعداد زیاد اعضای جمعیت می‌تواند کمک مناسبی با یافتن جواب بهینه باشد.

۲- جهش (Mutation)

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

$${V_i} = {X_{r1}} + F \cdot ({X_{r2}} – {X_{r3}})$$

که در آن:

• \({X_{r1}},{X_{r2}},{X_{r3}}\) اعضای تصادفی و متفاوت از جمعیت هستند.
• \({F}\) ضریب مقیاس است که معمولاً بین ۰.۴ تا ۱ قرار می‌گیرد.

۳- ترکیب (Crossover)

بعد از انجام جهش، crossover انجام می‌شود، بدین صورت که عددی تصادفی بین صفر و یک تولید شده و اگر عدد تولید شده کمتر از میزان نرخ کراس اور باشد عنصر مورد نظر در آن عضو از جمعیت، از قسمت جهش برداشته می‌شود در غیر اینصورت عنصر مورد نظر از مقدار اولیه عضو برداشته می‌شود اینقدر این کار تکرار می‌شود تا تمامی اعضای یک عضو یا از قسمت جهش خورده یا از مقادیر اولیه خود انتخاب گردند. یک بردار آزمایشی (Trial Vector) با ترکیب بردار هدف و بردار جهشی تولید می‌شود:

$${U_{i,j}} = \left\{ {\matrix{ {{V_{i,j}}} & {if\;ran{d_j} \le CR\;or\;j = {j_{rand}}} \cr {{X_{i,j}}} & {otherwise} \cr } } \right.$$

• \({{C}}\): نرخ کراس‌اور، معمولاً بین ۰.۳ تا ۰.۹
• \({{j_{rand}}}\): شاخص تصادفی برای تضمین حداقل یک تغییر

۴- انتخاب (Selection)

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

$${X_i} = \left\{ {\matrix{ {{U_i}} & {if\;f({U_i}) \le f({X_i})} \cr {{X_i}} & {otherwise} \cr } } \right.$$

• دانلود سورس کد الگوریتم تکاملی تفاضلی در متلب
• دانلود سورس کد حل TSP با الگوریتم تکاملی تفاضلی

فلوچارت الگوریتم DE

import numpy as np

def func(x):
    return sum(x**2)

def differential_evolution(func, bounds, pop_size=20, F=0.5, CR=0.7, generations=100):
    dim = len(bounds)
    pop = np.random.rand(pop_size, dim)
    for i in range(dim):
        pop[:, i] = bounds[i][0] + pop[:, i] * (bounds[i][1] - bounds[i][0])
    
    for gen in range(generations):
        for i in range(pop_size):
            r1, r2, r3 = np.random.choice([x for x in range(pop_size) if x != i], 3, replace=False)
            mutant = pop[r1] + F * (pop[r2] - pop[r3])
            cross = np.array([mutant[j] if np.random.rand() < CR else pop[i][j] for j in range(dim)])
            if func(cross) < func(pop[i]):
                pop[i] = cross
    return pop[np.argmin([func(ind) for ind in pop])]

# مثال استفاده
bounds = [(-5, 5)] * 5
best = differential_evolution(func, bounds)
print("Best solution:", best)

الگوریتم تکاملی تفاضلی یا همان الگوریتم DE جهت غلبه بر عیب اصلی الگوریتم ژنتیک (نبود جستجوی محلی) ارائه شده است، تفاوت اصلی بین الگوریتم ژنتیک و الگوریتم DE در عملگر انتخاب است. این الگوریتم برای مسائل پیوسته عملکرد بهتری نسبت به الگوریتم ژنتیک دارد ولی باید توجه داشت این الگوریتم فقط برای مسائل پیوسته قابل استفاده است.

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