قبل از پرداختن به حل مسئله ۸ وزیر با الگوریتم SFS بهتر است آشنایی مختصری با مسئله هشت وزیر داشته باشید. مسئله هشت وزیر از جمله مسائل کلاسیک در مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n وزیر یا معمای چند وزیر مطرح می‌شود. وزیر یا Queen (که در بازی‌های بین المللی اصطلاحی هم نام با معنی‌اش یعنی ملکه دارد ولی در کشور ما از اصطلاح وزیر استفاده می‌شود) مهره‌ای از مهره‌های بازی شطرنج است که می‌تواند در تمامی هشت جهت به هر تعداد خانه (تا زمانی که مهره‌ای مانع نباشد) حرکت کند.
اگر در این مسیرها مهره‌ای از حریف قرار گرفته باشد، آن مهره در معرض خطر حمله توسط وزیر قرار دارد یا به اصطلاح وزیر آن مهره را تهدید می‌کند. هدف از معمای هشت وزیر، قرار دادن ۸ مهره‌ی وزیر روی یک صفحه‌ی شطرنج خالی است، به قسمتی که هیچ مهره‌ای (وزیری)، مهره‌های (وزیرهای) دیگر را تهدید نکند. به عبارت دیگر، هشت وزیر باید به نحوی چیده شوند که هیچ‌کدام در یک سطر، یک ستون یا یک قطر قرار نداشته باشند. حل مسئله ۸ وزیر با الگوریتم SFS یکی از راه های حل این مسئله است.
الگوریتم جستجوی فراکتال تصادفی
الگوریتم جستجوی فراکتال تصادفی Stochastic Fractal Search که به اختصار SFS نیز نامیده می‌شود یکی از الگوریتم‌های فرا ابتکاری مهم است که با الهام از پدیده طبیعی رشد (growth) به وجود آمده است. این الگوریتم فراابتکاری جدید ارائه شده است که از مفهومی ریاضی به نام فراکتال استفاده می‌کند. با استفاده از ویژگی انتشار (Diffusion) که به طور منظم در فراکتال‌های تصادفی دیده می‌شود، ذرات در الگوریتم ارائه شده، فضای جستجو را کارآمدتر جستجو می‌کنند.
خاصیت یک شیء یا کمیتی که تشابه خود را در تمام مقیاس‌ها، به معنایی فنی، توضیح می‌دهد، فراکتال نامیده می‌شود. نظریه‌های فراکتال برای توصیف الگوهای هندسی در طبیعت است. نمونه‌ای از فراکتال‌ها شامل ساختارهایی از دانه‌های میکروسکوپی تا خوشه کهکشان‌ها وجود دارد.
فرکتال‌های تصادفی را می‌توان با اصلاح فرآیند تکرار از طریق قوانین تصادفی مانند خوشه‌های نفوذی (percolation clusters)، پیاده‌روی‌های خود اجتنابی (self-avoiding walks)، مناظر فراکتال (fractal landscapes)، مسیر حرکت براونی (trajectories of Brownian motion) و درخت براونی (Brownian tree) تولید کرد (دندریتی که با مدل‌سازی فراکتال‌های دندریتی تولید می‌شود).
درنهایت از رشد فراکتال (روش DLA) و نظریه پتانسیل برای طراحی الگوریتم فراکتال استفاده شده است. اگرچه جستجوی فراکتال در یافتن راه حل خوب عمل می‌کند، اما این رویکرد از معایبی رنج می‌برد. یکی از اصلی ترین آنها داشتن پارامترهای زیادی است که باید به خوبی به آنها پرداخته شود، و دیگری این که تبادل اطلاعات بین ذرات رخ نمی‌دهد.
حل مسئله ۸ وزیر با الگوریتم SFS جستجوی فراکتال تصادفی در متلب
در علوم کامپیوتر، ممکن است مسائل متفاوتی برای حل کردن وجود داشته باشد. این مسائل که معمولاً مسائل سخت یا NP_hard هستند، برای حل آنها از یک سری توابع و روش‌ها استفاده می‌شود که یکی از آنها توابع برازش یا فیتنس (Fitness) است.
در حل مسئله ۸ وزیر با الگوریتم SFS جستجوی فراکتال تصادفی نیز، از توابع Fitness استفاده شده است که به کمک کدهای الگوریتم جستجوی فراکتال تصادفی به بررسی و سپس حل مسئله ۸ وزیر با یک تعداد وزیر مشخص به زبان متلب پرداخته است.
این سورس کد به طور کلی دارای ۶ فایل است که فایل FSF.m کد اصلی بوده و فراخوانی توابع و تعیین تعداد وزیر مسئله در این سورس کد انجام می‌پذیرد. بخشی از سورس کد تابع فیتنس در زیر آورده شده است.
function out = Fitness(sol)
[~,sol]=sort(sol);
n=numel(sol);
% Transform the input chromosome into the chess field
field = zeros(n,n);
for i = 1:n
field(sol(i),i) = 1;
end
برای تهیه سورس کد کامل آن را خریداری نمایید. در ادامه خروجی مسئله با حل ۱۵ وزیر و همچنین پیش نمایش ویدئویی اجرای سورس کد آورده شده است.
تصویر خروجی
نظرات
فاطمه اسماعیلی
نظرات و دیدگاه های خود را با ما درمیان بگذارید.