بخشی از مقاله
چکیده
فرض کنید فمجموعه حروف الفبایی و Sفمجموعه اي از رشتهفها با طول یکسان روي الفباي فباشدچفمسئله نزدیکترین رشته، به دنبال رشتهفاي روي الفباي فمیفگردد که ماکزیمم فاصله همینگ آن رشته با دیگر رشتهفهاي موجود در Sفکمینه باشدچفمسئله نزدیکترین رشته یک مسئله NP-completeفاست که کاربرد فراوانی در ریاضیات زیستی و نظریه کد داردچفدر این مقاله از ایده کلونی مورچهفها براي ارائه یک الگوریتم هوشمند استفاده میفکنیم که مسئله نزدیکترین رشته را در زمان مناسبی حل میفکندچ
کلمات کلیدي: مسئله نزدیکترین رشته، سیستم کلونی مورچهفهاچ
-1 مقدمه
مسئله نزدیکترین رشتهل فدر سالیان اخیر به طور وسیع در ریاضیات زیستیه فو نظریه کدم فمطالعه و بررسی شده استچ6،8،2،3،13،5فاین مسئله کاربرد زیادي در علم زیست مانند طراحی PCR، طراحی کاوشگر ژنتیک و طراحی داروهاي ضد حساسیت داردچ4،7،1،9،10 فدر تمامی این کاربردفها وظیفه مشترك، طراحی یک DNA فجدید است که به تمامی رشتهفهاي داده شده شبیه باشدمسئله نزدیکترین رشته و دیگر مسائل مرتبط به آن از سري دسته مسائلفNP-completeفهستندچ11،12،6فتلاشفهاي زیادي براي کاهش پیچیدگی زمانی آنها صورت گرفته استچفعلیرغم سختی الگوریتم در عمل، طرح تقریبی زمان چندجمله ايتفروش موثر و طبیعی را ارائهدهدمیف که معمولاً راه حلی تقریباً بهینه براي مسئله را نتیجه میفدهدچغلفاین رویکرد هنگامی که ما به راه حلفهاي دقیقفو موثر نیاز داریم، کافی و کامل نیستچفبنابراین روشی ارائه شد که در زمان چند جمله اي . + با ثابت فرض کردن پارامتر یا پارامترهایی به حل مسئله میفپردازدچفدر اینجا عدد و فثابت فرض میفشوند و به این ترتیب رشد الگوریتم به وسیله - - فمحدود میفشودچهفدر حد بالایی براي حل مسئله نزدیکترین رشته و یک راه حل دقیق براي آن ارائه شده استچتفسپس یک حد پایین بهبود یافته و بهینه باپیچیدگی زمانی بررسی میفشود که در آن فتعداد خطا و فیک تابع دلخواه استچتلمحققان دو روش براي بهبود پیچیدگی زمانی این مسئله ارائه کردهفاندففالگوریتم رامفشدنی با پارامتر ثابت فو الگوریتم تقریبیچزلفروش پارامتر ثابت مسئله را در زمان - - - |Σ| - فحل میفکندچفالگوریتم تقریبی در زمان چند جمله اي به جواب میفرسدچفدر بررسی دیگر تغییراتی روي الگوریتم قبل اعمال شد و زمان آن به فبهبود پیدا کردچ ه فهمزمان با الگوریتمفهاي ترتیبی، الگوریتمفهاي موازي نیز براي حل مسئله مورد بررسی قرار گرفتندچفالگوریتم لیو ف فاز ایده الگوریتم ژنتیک استفاده کرده و راه حلی مناسب براي این مسئله ارائه میفدهدچشل فدر اکثر روشفهاي ذکر شده طول دنبالهفهاي ورودي در حد متوسط فرض شده استچفبراي رشتهفهاي ورودي با طول و تعداد زیاد روشی موازي ارائه شده است که الگوریتمی تقریبی میفباشدچحهففدر این مقاله، الگوریتمی فارائه شده است که با استفاده ازسیستم کلونی مورچهفها بدنبال فنزدیکترین رشته میفباشدچ فدر الگوریتم پیشنهادي ACS-CSP فم فهر مورچه بیانگر یک راه حل استچ فاین الگوریتم بر اساس فرومون باقیمانده در مسیر، نزدیکترین رشته را پیدا میفکندچ فدر این الگوریتم در هر مرحله بهترین حرف در تمامی رشتهفهاي ورودي انتخاب میفشودچفالگوریتم ACS-CSPفدر زمان مناسبی یک راه حل هوشمند و البته بهینه را براي حل مسئله نزدیکترین رشته ارائه میفکندچففساختار مقاله به این ترتیب خواهد بودففدر بخش هفبه بیان ریاضی مسئله نزدیکترین رشته میفپردازیم و نگاهی کوتاه به اصول و قواعد سیستم کلونی مورچهفها میفاندازیمچفالگوریتم ژنتیک مسئله CSPفدر بخش مفارائه میفشودچفدر بخش نسخه اصلی الگوریتم بیان میفشودچفتحلیل و مقایسه الگوریتم روي دادهفهاي آزمایشی در بخش ت فارائه میفشودچفدر نهایت در بخش ز، نتیجه گیري مقاله بیان میفگردد.
-2 نمادها:
- 1-2 بیان ریاضی مسئله:
فرض کنید که فمجموعه متناهی از نشانهفها و |Σ|فکاردینالیتی آن باشدتعریفچ فاگر x = x x … x فو y = y y … y فدو رشته به طول n فروي الفباي فباشند، فاصله همینگd - x, y - فبین دو رشته xفو yفبه این صورت تعریف میفشودd - x, y - = ∑ ε - x , y - فف، ε - x, y - = 0,1, =≠فپلژبه بیان دیگر فاصله همینگ برابر است با تعداد عدم تطابق بین دو رشتهچفف تعریف رسمی مسئله نزدیکترین رشته به صورت زیر است.وروديففاگر مجموعه s = {s s … s } فاز رشتهفها داده شده باشد به صورتیکه i = {1, … , n} ف، |s | ≤ L فو0 ≤ d ≤ Lهدفففرشته sفنزدیکترین رشته در مجوعه Sفاست اگر و تنها اگر رشته sفوجود نداشته باشد به نحوي که رابطهmax ,…, d - s , s - < max ,…, d - s , s - فبرقرار باشد.
- 2-2 سیستم کلونی مورچهها:
الگوریتمفسیستمفکلونی مورچهفها١فاز مطالعات و مشاهدات روي کلونی مورچهفهافالهام گرفته شده استچفاین مطالعات نشان دادهفاندفکه مورچهفها حشراتی اجتماعی هستند که در کلونیفها زندگی میفکنند و رفتار آنها بیشتر در جهت بقاء کلونی استچفیکی از مهمترین و جالبترین رفتار مورچهفها، رفتار آنها براي یافتن غذا استچفمورچهفها هنگام حرکت از یک مکان به مکان دیگر مقداري فرومون بر روي زمین به جاي میفگذارندچففرومون ماده شیمیایی است که باعث جذب مورچهفهاي دیگر میفشودچفهر چه میزان فرومون موجود در یک مسیر زیادتر باشد، مورچهفهاي بیشتري از آن عبور میفکنندچفبه این ترتیب فرومون موجود در مسیر بلندتر کاهش میفیابد و مورچهفهاي بیشتري به سمت مسیر کوتاه تر جذب میفشوند.
