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

مجله فناوری اطلاعات در طراحی مهندسی

مقاله 6، دوره 5، پاییز و زمستان - شماره پیاپی 52، بهمن 1393، صفحه 84-108   

نوع مقاله: مقاله پژوهشی

چکیده

چکیده: الگوریتم ژنتیک در حل بسیاری از مسائل بهینه سازی الگوریتم قدرتمندی است که کارایی آن به میزان زیادی تحت تأثیر انتخاب صحیح پارامترها و عملگرهای آن نظیر تعداد کروموزوم جمعیت، نوع عملگر تقاطع، جهش و... قرار دارد. تا کنون روشهای مختلفی به منظور افزایش کارایی الگوریتم ژنتیک پیشنهاد شده است. در این مقاله برای اولین بار از یک روش محاسبه برازندگی جدید مبتنی بر ماشین خودکار سلولی(CA (به منظور افزایش کارایی الگوریتم ژنتیک (GA (استفاده شده است. الگوریتم ترکیبی پیشنهادی در نهایت به منظور تعیین مینیمم 5 تابع شناخته شده در زمینۀ بهینهسازی با 5 و 10 متغیر مورد استفاده قرار گرفت. نتایج نشان داد که الگوریتم ترکیبی GA-CA در مقایسه با الگوریتم ژنتیک استاندارد از دقت بیشتری در پیدا کردن بهترین مینیمم توابع مورد بهینه سازی برخوردار است. همچنین الگوریتم ترکیبی GA-CA به لحاظ زمان رسیدن به بهترین مینیمم گلوبال ( زمان همگرایی) در حدود 5 برابر کمتر از الگوریتم ژنتیک استاندارد می باشد.

کلیدواژه‌ها

بهینه سازی؛ الگوریتم ژنتیک؛ ماشین خودکار سلولی یک بعدی

اصل مقاله

1 -مقدمه ١ الگوریتم ژنتیک ، الگوریتم قدرتمندی است که میتواند در حل بسیاری از مسائل بهینه سازی مفید باشد. البته کارایی این الگوریتم به میزان بسیار زیادی وابسته به انتخاب مناسب، تعداد و نوع پارامترهای آن به عنوان مثال اندازة جمعیت، روش انتخاب کروموزومها، نوع عمل تقاطع، احتمال تقاطع، احتمال جهش و... می باشد[1 .[ تا کنون روشهای زیادی به منظور افزایش کارایی محاسباتی الگوریتم ژنتیک پیشنهاد شده است. Juan, Liu وهمکاران از یک روش جستجوی آشوبی به منظور افزایش دینامیکی اندازة جمعیت اولیه و افزایش تنوع و بهبود کارایی در حل مسئله استفاده کردند [2 .[ Hrstka Ondrej و همکاران از یک اپراتور دیفرانسیلی در عمل تقاطع الگوریتم ژنتیک استفاده کرده اند[3.[Andrea. J و همکاران از کاهش تطبیقی بازه مربوط به هر متغیر و استفاده از فاکتور مقیاس در محاسبه احتمالات تقاطع در الگوریتم ژنتیک استفاده کرده اند[4 .[Bakar Abu Sultan Md و همکاران از یک تکنیک عددگذاری یکتا به منظور نمایش جمعیت اولیه درالگوریتم ژنتیک استفاده کردند و نشان دادند که با این روش، تنوع جمعیت بهبود مییابد و کارایی الگوریتم ژنتیک در حل مسائل افزایش پیدا میکند .[5] Caponetto Riccardo و همکاران از دنبالههای آشوبی در تمامی بخشهای الگوریتم ژنتیک از 1- Crossover Operator قبیل تولید جمعیت اولیه، مرحله انتخاب، تقاطع و جهش استفاده نمودند [6 .[ J. Wu و همکاران از ماشین خودکار سلولی دو بعدی به منظور افزایش کارایی الگوریتم ژنتیک استفاده کردهاند. آنها الگوریتم ترکیبی GA-CA پیشنهادی را در بهینه سازی طراحی یک ساختار مکانیکی به نحوی مورد استفاده قرار دادند که کروموزومهای هر جمعیت با استفاده از فاصله همینگ میان کروموزوم ها و مقدار برازندگیشان روی سلولهای ماشین خودکار سلولی دو بعدی نگاشت داده می شوند و بدین ترتیب انتخاب هرکدام از کروموزوم ها در مراحل بعد بر مبنای ساختار ماشین خودکار سلولی دوبعدی کنترل میشود[7 .[همچنین در تحقیق دیگری Xu Yufa و همکاران از ماشین خودکار سلولی دو بعدی "بازی زندگی" به عنوان عملگر تقاطع در الگوریتم ژنتیک استفاده کرده و نشان دادند که کارایی الگوریتم در بهینه سازی وزنهای شبکه عصبی بهبود یافته است[8 .[ در این مقاله با توجه به خواص قانونمندی محلی، خودسازماندهی و خودتولید کنندههای ماشین خودکار سلولی، برای اولین بار از یک روش محاسبۀ برازندگی جدید مبتنی بر ماشین خودکار سلولی(CA (به منظور افزایش کارایی الگوریتم ژنتیک (GA (در یافتن مینیمم گلوبال استفاده شده است. سپس الگوریتم ترکیبی حاصل به منظور بهینهسازی چند تابع بهینهسازی شناخته شده مورد استفاده قرار گرفته است. این مقاله به سه بخش کلی تقسیمبندی میشود. در بخش اول، خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 85 ساختارها و پارامترهای ماشین خودکار سلولی و الگوریتم ژنتیک مورد استفاده در الگوریتم ترکیبی پیشنهاد شده GA-CA تعریف شدهاند. در بخش دوم، ساختار الگوریتم ترکیبی پیشنهادی GA-CA ارائه می شود و در نهایت در بخش سوم کارایی الگوریتم ترکیبی GA-CA در حل توابع شناخته شده در زمینه بهینهسازی مورد بحث و بررسی قرار میگیرد و با الگوریتم ژنتیک استاندارد مقایسه می شود. 2 -روش کار در این مقاله هدف تعیین مینیمم گلوبال توابع استانداردی است که از شکل کلی ذیل پیروی میکنند. Minimizef(x), x=( x1, x2,…, xn)∈ ܵ (1) که در این رابطه (x(f تابع مورد بهینه سازی و xn,…, x2, x1 متغیرهای تابع اند و ϵR S n نشاندهندة فضای جستجوی n بعدی (به تعداد متغیرهای تابع مورد بهینه سازی) است که محدود به کرانههای استاندارد در نظر گرفته شده برای تابع مورد بهینه سازی است. بنابراین [ , ] L R i i x x  S است که در آن L R i i i x  x  x است. در ادامه، بخشهای مختلف الگوریتم ترکیبی پیشنهادی برای تعیین مینیمم گلوبال توابع مورد بهینه سازی در این مقاله معرفی خواهد شد. 2-1 -ماشین خودکار سلولی ماشین خودکار سلولی دستهای از سیستمهای ریاضی قطعی و گسسته زمانی است که با تعاملات و شکلهای موازی تکامل مشخص میشود. ماشینهای خودکار سلولی همچنین دسته بزرگی از سیستمهای پیچیده هستند که در آن اجزاء کاملاً شناخته شده و به لحاظ درک، سادهاند؛ اما رفتار و عملکرد کلی سیستم به دلیل تعاملات غیرخطی محلی اجزاء دارای توضیح ساده ای نیست [9 .[ اولین بار وون نیومن در سال 1950 اتوماتای سلولی را به عنوان مدل سادهای به منظور مدلسازی رفتار خود تکثیری و خودسازماندهی بیولوژیکی ابداع و ارائه کرد[10 .[ماشین خودکار سلولی در واقع مدلی از سیستمهای پیچیده و فرآیندهایی است که دارای تعداد زیادی از اجزاء مشابه، ساده و دارای تعاملات محلی است. مطالعه بر روی ماشینهای خودکار سلولی در سالهای اخیر به دلیل تواناییشان در تولید الگوهای بسیار پیچیده از قوانین ساده، بسیار مورد توجه قرار گرفته است. به عبارت دیگر ماشینهای خودکار سلولی توانسته اند بسیاری از الگوهای اساسی رفتارهای پیچیدة خودسازمانده و مشارکتی که در سیستمهای واقعی مشاهده میشود را مدلسازی کرده و نشان دهند، [9 [و [11.[ کاربردهای زیادی از ماشین خودکار سلولی در فیزیک، زیست شناسی، شیمی، بیوشیمی و زمین شناسی و... گزارش شده است. به عنوان مثالهایی خاص از پدیدههایی که با ماشین خودکار سلولی مدل شدهاند میتوان به رشد شاخهای کریستالها [ 12 [و [13 [تئوریهای اکولوژیکی، مطالعه تکامل، بازسازی و خود تولیدکنندگی DNA درون سلولها اشاره کرد [16 [و [15 [و [14 [مدلسازی رشد ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 86 آتشسوزی در جنگلها [17 [و [18 ،[الگوهای فعالیت الکتریکی شبکههای نورونهای عصبی [19 ،[رشد تومورهای سرطانی [20] ،[21 [و [22 ،[همچنین ساخت رباتهایی از مکعب که بتوانند با مکعب، نظیر خود را بسازند [23 [و خود را تعمیر کنند، اشاره نمود. لازم به ذکر است که ماشین خودکار سلولی می تواند طیف گستردهای از دینامیکهای رفتاری (پیچیدگی، خودسازماندهی، آشوبی، پریودیک، نقطه تعادل و ...) را تولید کند. 2-1 -1 -معرفی متغیرهای ریاضی ماشین خودکار سلولی یک ماشین خودکار سلولی محدود یک بعدی ℒ با N سلول با  و ߶و r مشخص می شود که: { , ,..., } -1    1  2  N مجموعۀ محدودی از (t)   {0,1,2,..., k  1} i  حالت هاست و مقدار سلول i ام ماشین خودکار سلولی در لحظه t و k تعداد حالتهای ممکنی است که یک سلول در هر لحظه می تواند اختیار کند. 2 -ݎ تعداد نزدیکترین همسایگی های سلول است. 3 ߶ -قانون تعامل میان سلولها در هر مرحله است و   i t i  ( 1) ( {i})= ( ( ),..., ( ),..., (t)) i r t i t ir      s s ,  : 2r1  که {i{ࣨ مجموعهای شامل سلول iام و همسایههایش میباشد. در حالت کلی تعداد 2 r  1 k k قانون تعامل وجود دارد. به منظور تعیین وضعیت سلولهای مرزی (سلولهای قرار گرفته در مکانهای 1 و ܰ ) در زمانt،در این مقاله فرض شده است که در دو طرف شبکه سلولی با ܰ سلول، سلولهایی با مقادیر پیش فرض صفر وجود دارند. بنابراین برای یک ماشین خودکار یک بعدی با، در هر طرف از شبکه سلولی با N سلول، دو سلول فرضی و غیر قابل مشاهده وجود دارند که به صورت ذیل دارای مقادیر صفر می باشند. ( ) 0 1 ( ) 0 ( ) 2 ( ) 1        t t t N t N     (2) مطابق با رابطه (2 (شرط اولیه (حالت سلولها در 0 = ݐ ) برای یک ماشین خودکار یک بعدی به صورت ذیل خواهد بود.  ( 0) (0)... (0)00 2 (0) 1 00 t N     پارامترهای ماشین خودکار سلولی مورد استفاده در این مقاله در جدول (1 (قابل مشاهده است. جدول (1 :(مقادیر پارامترهای ماشین خودکار سلولی مورد استفاده در این مقاله فضای حالت سلولی گسسته ख یک بعدی شعاع همسایگی r 2 2 k پارامتر {1,0 {فضای مقدار محلی  شرایط مرزی 32 تعداد قوانین دینامیکی ࣘ 2 4.2950 e+009 یا ( ) 0 1 ( ) 0 ( ) 2 ( ) 1        t t t N t N     خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 87 2-2 -الگوریتم ژنتیک الگوریتم ژنتیک، الگوریتمی است الهام گرفته شده از نظریۀ تکامل داروین و علم نوپای ژنتیک که اولین بار در کاربردهای مهندسی و توسط فردی به نام جان هلند، متخصص علوم کامپیوتر دانشگاه میشیگان در سال 1975 پیشنهاد گردید [24 .[الگوریتمهای ژنتیک که بر اساس بقای برترینها یا انتخاب طبیعی استوارند،دستۀ بزرگی از الگوریتمهای تکاملی محسوب میشوند که میتوانند با استفاده از تکنیکهایی که از تکامل طبیعی الهام گرفته است به منظور تولید پاسخ (نقاط بهینه) در مسائل بهینه سازی مورد استفاده قرار گیرند و از این رو ابزار سودمندی در بازشناسی الگو، انتخاب ویژگی، درک تصویر و یادگیری ماشین محسوب می شود. 2 -2 -1 -معرفی متغیرهای ریاضی الگوریتم ژنتیک الگوریتم ژنتیک استفاده شده در این مقاله به شکل کلی: در که شود می تعریف GA  (I, , , s, l, , ) آن: 1 -ܫ فضای کروموزوم هاست. 2 -R l:  نشان دهندة تابع (نگاشت) 1 برازندگی است که مقادیر حقیقی برازندگی را به 2 هر کروموزوم به نحوی نسبت میدهد. با توجه به اینکه در این مقاله هدف، مینیمم کردن مقادیر 1- Mutation 2- Crossover برازندگی است، هر چه برازندگی جواب مسئله کمتر باشد، شانس انتخاب آن پاسخ بیشتر است. به عبارت دیگر داریم: x x   x   x x x  l (3) 2 , 1 ), 2 ) ( 1 ( 1 2  3 - مجموعهای شامل اپراتورهای احتمالاتی است که هر کدام توسط پارامترهای ویژه ای که در مجموعه اعداد حقیقی قرار دارند کنترل میشوند. متداولترین این اپراتورها اپراتور جهش و تقاطع است. -4     s l l  l  (  : ( پارامتر انتخاب است که به منظور انتخاب not Bookmark! Error  .defined تا کروموزوم از میان !Error کروموزوم    یا Bookmark not defined.  مورد استفاده قرار میگیرد. ߤ تعداد کروموزومهای والد و not Bookmark! Error .defined تعداد کروموزوم های فرزند است. l : I  {true, false}نهایت در- 5  معیار توقف الگوریتم ژنتیک است. لازم به ذکر است که در الگوریتم ژنتیک  استاندارد جمعیت کروموزومی اولیه به P(0)  I صورت رندم در فضای حل مسئله تولید میشود. 2-3 -مراحل کار الگوریتم ترکیبی GA-CA در این قسمت بخشهای مختلف الگوریتم ترکیبی پیشنهادی به منظور حل مسائل بهینهسازی مشخص میشود. ویژگی این الگوریتم، ترکیبی از ویژگیهای ساختاری الگوریتم ژنتیک؛ یعنی تکاملی بودن و ماشین خودکار  ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 88 سلولی، یعنی خودسازماندهی، خودتکثیری و قانونمندی محلی است. کلیۀ مراحل کار الگوریتم عبارتند از: 1 -ابتدا جمعیت کروموزومی اولیه A با M کروموزوم به صورت رابطه (5 (تولید می شود که هر کروموزوم یک رشته دودویی با طول l و معادل با قانونی است که باید به ماشین خودکار سلولی داده شود. از آنجا که شماره قانون داده شده به ماشین خودکار سلولی باید صحیح باشد، لذا رشتۀ کروموزومهای دودویی جمعیت اولیه الگوریتم ژنتیک استاندارد (سطرهای ماتریس A( پس از تبدیل به عدد دهدهی گرد میشوند تا بخش اعشار آنها حذف شود و سپس عدد گرد شدة حاصل، به عنوان شماره قانون ெ ܴبه ماشین خودکار سلولی داده می شود. لازم به ذکر است که در این مقاله جمعیت کروموزومهای اولیه به صورت رندم انتخاب می شوند:              Ml aM aM a l a a a l a a a T A A A AM ... 1 2 ... ... ... ... 2 ... 21 22 1 ... 11 12 ,..., ) 2 , 1 (  (4) T R R R ,..., RM ) 2 , 1  (  که ଵ ܴو ଶ ܴو ... شماره قانونهایی است که به ماشین خودکار سلولی داده خواهد شد. 2 -مرحلۀبعدی که تخصیص و مقیاس بندی 1 مقادیر برازندگی کروموزوم های جمعیت اولیه است ابتدا به صورت ذیل، مقدار برازندگی هر 1- Fitness Scaling کروموزوم مشخص و سپس مقادیر برازندگی مقیاس بندی می شوند. - قانونهای ெܴتولید شده در مرحله اول به صورت تک تک به ماشین خودکار سلولی که شرط اولیۀ آن (0 = ݐ)⃗ߪمتناسب با کران متغیرهای تابع مورد بهینه سازی تعیین خواهد شد، داده می شود و ماشین خودکار سلولی پس از دریافت هر قانون و اعمال آن به شرط اولیه با در نظر گرفتن جدول ذیل، شروع به کار کرده و به تعداد  تا رشته دودویی تولید میکند. برای این کار ابتدا شماره قانون ெ ܴبه شکل دنباله ... ) باینری 1 2 3 ( 32 یک هر که میشود تبدیل      از اعضای این دنباله به صورت جدول (2 (به هر یک از 32 حالت ممکن چهار سلول همسایۀ سلول ( )) امi 2 ( ) 1 ( ) ( ) 1 ( ) 2 ( t i t i t i t i t i    ماشین      خودکار سلولی ( با 2 =r ( نسبت داده میشود و با )  i سپس حالت سلول i ام در مرحلۀ بعد (1  t( توجه به این جدول مشخص می شود. خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 89 r = قوانین محلی ساده برای CA با 2 : ( 2 جدول ( ( t  1 ) i ( )  2 t i  ( )  1 t i  ( t )  i ( )  1 t i  ( )  2 t i   1 1 1 1 1 1  2 1 1 1 1 0  3 1 1 1 0 1  4 1 1 1 0 0  5 1 1 0 1 1  6 1 1 0 1 0  7 1 1 0 0 1  8 1 1 0 0 0  9 1 0 1 1 1  10 1 0 1 1 0  11 1 0 1 0 1  12 1 0 1 0 0  13 1 0 0 1 1  14 1 0 0 1 0  15 1 0 0 0 1  16 1 0 0 0 0  17 0 1 1 1 1  18 0 1 1 1 0  19 0 1 1 0 1  20 0 1 1 0 0  21 0 1 0 1 1  22 0 1 0 1 0  23 0 1 0 0 1  24 0 1 0 0 0  25 0 0 1 1 1  26 0 0 1 1 0  27 0 0 1 0 1  28 0 0 1 0 0  29 0 0 0 1 1  30 0 0 0 1 0  31 0 0 0 0 1  32 0 0 0 0 0  ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 90 که شمارهெ ܴمربوط به M امین قانون به صورت رابطۀ (6(محاسبه می شود.      j j binary j 32 2 32 1 ) 32 ... 1 ( 2 3      RM  [1 , 4.2950 e  9] (5) همانطور که در بخش 3 ) بخش نتایج ) نیز اشاره خواهد شد، شرط اولیۀ پیشنهادی برای اتوماتای سلولی در این مقاله، با توجه به معادل ௜ݔ ௅ تابع مورد بهینه سازی دودویی کران پایین که شامل ௅ܰ بیت میباشد، در نظر گرفته شده است. البته همانطور که در ادامه نشان خواهیم داد، حساسیت به شرایط اولیه الگوریتم ترکیبی GA-CA در فرآیند پیدا کردن مینیمم گلوبال با توجه به تعدد قوانین ماشین خودکار سلولی بسیار پایین است. برای یک تابع مورد بهینه سازی،n متغیرة تقسیمبندی رشتۀ دودویی ماشین خودکار سلولی در لحظه، وt به شکل کلی رابطۀ (7 (است: .... ( ) 1 1 1 2 ( ) 0 ( ) 1 ( )   x t (t) L N (t)...σ flt  t  t  t σ (t)σ (t)...σ   ... ( ) 2 ( )... ( )... ( ) ( 1) 2 ( ) ( 1) 1   x t t L nN t n flt t L n N t L n N         ( ) ( ) (6) 1 2 t t nNL nNL    همانطور که قبلاً نیز گفته شد، در این مقاله شرایط مرزی هر رشته باینریی در ماشین خودکار سلولی در هر لحظه t مقدار ثابت صفر در نظر گرفته شده است ( رابطه (8 .( ( ), ( ), ( ), ( ) 0 0 1 1 2     t t t t L L nN nN     (7) همچنین هر رشته باینری تولید شده توسط ماشین خودکار سلولی باید به معادل دهدهی تبدیل شود که(ݐ)௡ݔدر رابطۀ(7(معادل دهدهی متغیر n ام تابع مورد بهینه سازی در لحظهt است و داریم: ( ( )....) ( 1) 2 Dec bin t NL  n   x (t) صحیح قسمت n Dec bin t t n L ( flt ( )... nN ( ))  x (t) اعشاری قسمت n (ݐ)௡ است و (ݐ) بیت علامت متغیر ݔ ಽାଵ و ே)ଵ(௡ିߪ داریم:       0 ( ) is positive number 1 ( ) is negative number ( ) ( 1) 1 t n if x t n if x t L n N  لازم به ذکر است در صورتی که کران پایین ௅௜ݔ دارای بخش اعشاری نباشد، تعداد بیتهای قسمت اعشاری معادل برای تمامی متغیرهای ௜ݔ ݊ , ... ,2,1), ݅ = ݐ) در شرط اولیه ماشین خودکار سلولی را به صورت دلخواه و با توجه به دقت مورد نیاز در نظر گرفته و به جای بیتهای مربوط به آن قسمت، یعنی عدد 0 قرار می دهیم. که xi(t) , i=1,2,…,nمتغیرهای دهدهی مقادیر سپس توسط ماشین خودکار سلولی تولید شدهاند به خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 91 ݂௢௕௝ صورت رابطۀ (9 (به تابع مورد بهینهسازی6 داده میشوند و ارزش هر کدام مشخص میشود: ( ),..., ( )) (8) 2 ( ), 1 ( ) ( t n x t x t x obj t f val f  پس از محاسبۀ تابع (ݐ)௟௔௩ ݂برای هر رشته باینری از  تا رشته باینری، تولید شده توسط ماشین خودکار سلولی، در نهایت میان تمامی این مقادیر به صورت رابطه (10 (مینیمم گرفته میشود و مقدار این مینیمم به عنوان مقدار برازندگی(ܯܴ)Φ کروموزوم ( قانون ெ ܴماشین خودکار سلولی) M ام در جمعیت اولیه الگوریتم ژنتیک در نظر گرفته می شود. Φ(ܴܯ) ݂൛݊݅݉ = (9) ൟ∆ :1 = ݐ|(ݐ)݈ܽݒ انتخاب- 1 -3-2 در این مقاله از اپراتور انتخاب نمونه برداری 7 تصادفی جامع استفاده شده است. در این روش که توسط Baker پیشنهاد شده است، ابتدا احتمال انتخاب هر یک از کروموزومهای جمعیت کروموزومی اولیه با استفاده از رابطه (11 (و بر اساس مقدار برازندگی هر کروموزوم محاسبه می شود: (10)      M j j R i R F Ri 1 ( ) ( ) ( ) که در این رابطه ( ) i R  مقدار برازندگی i کروموزوم ( قانون ماشین خودکار سلولی) R و 1- Objective function 2- Stochastic Universal Sampling (SUS) ( ) i R F احتمال انتخاب کروموزوم است. پس از آن کروموزومها با توجه به احتمال انتخابشان و از بیشترین احتمال تا کمترین احتمال در کنار هم به نحوی در محدودة 0 و 1) از احتمال 0 تا احتمال 1 (مرتب میشوند و سپس یک عدد رندم ݎݐ݌ در محدودة Nind/1 0] [که (Nind تعداد کروموزومهایی است که میخواهیم انتخاب شوند) تولید میشود. بعد از آن نشانگرهایی به ترتیب در مکانهای ,ptr ptr.Nind,…, 2ptr قرار میگیرند و در نهایت کروموزوم هایی که نشانگر در آنها قرار گرفته است، انتخاب می شوند. تقاطع- 2 -3-2 بعد از اینکه بهترین کروموزومها (قوانین ماشین خودکار سلولی) از میان جمعیت اولیه کروموزومی انتخاب شدند، دو تا از این 1 کروموزومها (قوانین ماشین خودکار سلولی) R R2 مطابق با احتمال انتخابشان، به عنوان و کروموزوم ( قانون) های والد انتخاب می شوند و 2 با استفاده از عملگر تقاطع I  I c : با احتمالpc با هم ترکیب میشوند و دو کروموزوم (قانون) فرزند ' 1 ' و R 2 R را تولید میکنند که ممکن است از والدین بهتر باشند. در این مقاله از عملگر تقاطع تک نقطهای استفاده شده است. جهش- 3 -3-2 پس از انجام مراحل انتخاب و تقاطع، عملگر به pm احتمال با m : I  I جهش کروموزومومها (قوانین) اعمال می شود تا از عدم یکسان بودنشان اطمینان حاصل شود. در ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 92 این مقاله از الگوریتم ژنتیک اپراتور جهش گوسی استفاده شده است. اصول و نحوة عملکرد این نوع عملگر در مرجع [25 [ارائه شده است. 2-3 -4 -شرط توقف الگوریتم ژنتیک شرایط توقف الگوریتم ژنتیک مورد استفادة در این مقاله یکی از دو شرط ذیل است: 1 -میانگین وزن دار مقدار برازندگی کروموزومهای موجود در جمعیت جدید تولید 8 شده کمتر از 6-1e شود، 2 -تعداد تولیدهای G به مقدار مشخص شده Gmax برسد. (11)      false otherwise true if G G l P G ( ( )) max در این رابطه، G شماره تولید وGmax بیشترین تعداد تولید است. پس از اتمام کار الگوریتم ژنتیک، قانون برتر ماشین خودکار سلولی که کمترین مقدار برازندگی را در میان سایر قوانین داشته است، به عنوان خروجی برنامه انتخاب میشود و مقدار برازندگی آن به عنوان مینیمم تابع مورد بهینهسازی در نظر گرفته میشود. شکل (1 (به صورت خلاصه الگوریتم پیشنهادی در این مقاله را نشان میدهد. 3 -نتایج در این قسمت از 5 تابع شناخته شده موجود در جدول 3 به عنوان توابع مورد بهینهسازی که باید نقطه مینیمم آنها تعیین شود، استفاده شده 1- Generation است و نقش پارامترهای مختلف الگوریتم ترکیبی GA-CA در تعیین میزان کارایی الگوریتم مورد بحث و بررسی قرار خواهد گرفت. شکل (1 :(مراحل مختلف الگوریتم ترکیبی GA-CA خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 93 جدول (3 :(توابع مورد بهینه سازی مورد استفاده ( n تعداد متغیرهای تابع است) مینیمم گلوبال تابعmin f محدوده متغیرهای تابع توابع مورد بهینه سازی  32.768   32.768 0 i f1 Ackley x  2.048   2.048 0 i f2 Rosenbrock x  5.12   5.12 0 i f3 Rastrigin x  500   500 -418.9829n i f Schwefel x 4  600   600 0 i f5 Griewangk x در این جدول n,…,2,1 =i است که n بعد (تعداد متغیرهای پیشنهادی برای توابع) میباشد و در این مقاله تمامی توابع با ابعاد 5 و 10 مورد استفاده قرار گرفتهاند. لازم به ذکر است که روابط مربوط به هر یک از توابع در ضمیمه آورده شده است. همانطور که قبلاً نیز اشاره شد، شرط اولیه برای اتوماتای سلولی مورد استفاده در بهینه سازی تمامی توابعn متغیره، با توجه به معادل ௜ݔ ௅ دودویی قسمتهای کران پایین تابع مورد بهینه سازی در نظر گرفته شده است. تعداد رشتههای باینری  تولید شده توسط ماشین خودکار سلولی نیز در بهینه سازی همۀ توابع 30 و شعاع همسایگی r برابر2 در نظر گرفته شده است. همچنین محدودة جمعیت اولیه برای [ , ] الگوریتم ژنتیک استاندارد L R i i x x و برای الگوریتم ژنتیک ترکیبی با ماشین خودکار سلولی [1 , 4.2950e  9] در نظر گرفته شده است. احتمال جهش در الگوریتم پیشنهادی و در تمامی آزمایشات مقدار 1/0 در نظر گرفته شده است. هر کدام از این دو الگوریتم 100 بار برای هر تابع مورد بهینه سازی مورد استفاده قرار گرفته اند و میانگین و واریانس بهترین مقادیر برازندگی به دست آمده با این دو الگوریتم به عنوان معیار ارزیابی کارایی آنها محاسبه شده است. 3-1 -بررسی اثر احتمال تقاطع pc جدول (4 (اثر احتمال تقاطع pc را بر پیدا کردن مینیمم توابع استاندارد نشان می دهد. ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 94 جدول (4 :(بررسی اثر احتمال تقاطع pc بر پیدا کردن مینیمم توابع استاندارد در 100 بار اجرای الگوریتم ترکیبی .CA-GA GA-CA الگوریتم ترکیبی الکوریتم ژنتیک استاندارد توابع مورد بهینه سازی Pc=0.1 Pc=0.5 Pc=0.8 Pc=0.9 Pc=0.1 Pc=0.5 Pc=0.8 Pc=0.9 8.8818e-16 8.8818e-16 8.8818e-16 8.8818e- 16 2.5707 0.7783 0.3086 0.4233 میانگین f1 (N=5) 0.4998 0.4775 0.1955 0.2548 0 0 0 0 واریانس 8.8818e-16 8.8818e-16 8.8818e-16 8.8818e- 16 4.5328 2.6661 1.7323 1.9051 میانگین f1 (N=10) 0.4571 0.4410 0.3585 0.3925 0 0 0 0 واریانس 1.5056 1.1466 1.3490 1.4578 0 0 0 0.3088 میانگین f2 (N=5) 0.6644 0.6818 0.6884 0.7873 0 0 0 0.4850 واریانس 8.8799 4.4232 4.3928 4.4115 0 0 0 0.4901 میانگین f2 (N=10) 1.6377 1.5836 1.3886 1.4872 0 0 0 0.5050 واریانس 4.1458 0.2005 0.0694 0.1151 0 0 0 0 میانگین f3 (N=5) 1.4176 0.2285 0.0840 0.1550 0 0 0 0 واریانس 29.3992 5.8505 2.4781 2.9068 0 0 0 0 میانگین f3 (N=10) 5.5794 1.8609 1.0280 1.1112 0 0 0 0 واریانس -2.0947e+3 -2.0943e+3 -2.0917e+3 - 2.0907e+3 - 1.5365e+3 -1.3412e+3 -1.8172e+3 - 1.7458e +3 میانگین f4 (N=5) 1.1213e+3 855.1495 873.7160 14.1 0.2791 0.5455 7.1569 983.050 2 واریانس -4.1897e+3 -4.1883e+3 -4.1856e+3 - 4.1895e+3 - 2.0613e+3 -2.3097e+3 -3.3396e+3 - 2.9570e +3 میانگین f 4 (N=10) 1.5152e+3 1.2698e+3 1.1275e+3 0.4491 0.3094 1.1099 8.2472 1.1901e +3 واریانس 0.1906 0.1213 0.1165 0.2536 0 0 0 0 میانگین f5 (N=5) 0.1059 0.0795 0.1068 0.1436 0 0 0 0 واریانس 1.6112 1.2419 1.0651 1.4032 0 0 0 0 میانگین f5 (N=10) 0.5425 0.3381 0.2661 0.4922 0 0 0 0 واریانس خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 95 از آنجا که در الگوریتم ترکیبیGA-CA هر یک از کروموزوم های جمعیت اولیه، قانون (rule (ای است که باید به شرط اولیه CA اعمال شود و  تا رشته باینری تولید کند تا برازندگی آن قانون تعیین شود، بنابراین میتوانیم بگوییم این کار معادل حالتی است که تعداد کروموزومهای MH جمعیت اولیه الگوریتم ژنتیک استاندارد MH تعداد کروموزو باشد که مهای اولیه در الگوریتم ژنتیک موجود در الگوریتم ترکیبی -CA GAاست؛ از این رو به منظور مقایسۀ صحیح میان الگوریتم ژنتیک استاندارد و الگوریتم ترکیبی GA-CA تعداد کروموزومها (قوانین) های اولیه در الگوریتم ترکیبی GA-CA را 20 و تعداد کروموزومهای جمعیت اولیه را در الگوریتم استاندارد sGA برابر 600 ) یا 20×30 (در نظر گرفتهایم و تعداد تولیدهای GA در هر دو الگوریتم را نیز 100 قرار داده ایم. همانطور که در جدول (4 (دیده می شود، الگوریتم ترکیبی GA-CA به ازای همۀ مقادیر pc مینیمم گلوبال توابع f1 و f3 و f5 را به صورت دقیق پیدا کرده است. همچنین الگوریتم ترکیبی GA-CA برای تابع f2 با 5=N و 10=N و به ازای مقادیر احتمال را گلوبال مینیمم 0.8pc=0.1, pc=0.5 , pc= تقاطع به صورت دقیق پیدا کرده است. برای تابع f4 نیز الگوریتم ترکیبیGA-CA نزدیکترین پاسخ را به مینیمم گلوبال به ازای 5.0=pc پیدا کرده است. الگوریتم استاندارد sGA به ازای همۀ مقادیر pc در پیدا کردن مقدار مینیمم در مقایسه با الگوریتم GA-CA دارای خطای قابل توجهی است؛ اما این الگوریتم با 8.0=pc برای همۀ توابع نزدیکترین پاسخ به مینیمم گلوبال را نسبت به سایر مقادیر pc پیدا کرده است. همچنین هر چه درجه تابع افزایش پیدا میکند، خطای الگوریتم استاندارد sGA در پیدا کردن مینیمم گلوبال تابع افزایش می یابد. 3-2 -بررسی اثر احتمال جهشpm جدول (5 (اثر احتمال جهشpm را بر پیدا کردن مینیمم توابع استاندارد نشان می دهد. با توجه به دلایل ذکرشده در بخش قبل، تعداد کروموزومها (قوانین) اولیه در الگوریتم ترکیبی GA-CA را  و تعداد کروموزومهای جمعیت اولیه را در MH  الگوریتم استاندارد sGA برابر در نظر گرفتهایم. همچنین مقدار pc را بهترین مقدار انتخاب شده در بخش 3-1 یعنی 5.0=pc در نظر گرفته ایم. ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 96 جدول (5 :(بررسی اثر احتمال جهشpm بر پیدا کردن مینیمم توابع استاندارد در 100 بار اجرای الگوریتم ترکیبی .CA-GA GA-CAالگوریتم ترکیبی الکوریتم ژنتیک استاندارد توابع مورد بهینه سازی Pm=0.1 Pmc=0.5 Pm=0.8 Pm=0.9 Pm=0.1 Pm=0.5 Pm=0.8 Pm=0.9 8.8818e-16 8.8818e-16 8.8818e-16 8.8818e- 16 2.8707 0.6783 0.3186 0.3233 میانگین f1 (N=5) واریانس 0.3999 0.3775 0.1905 0.2648 0 0 0 0 8.8818e-16 8.8818e-16 8.8818e-16 8.8818e- 16 3.5328 2.8661 1.7323 1.9051 میانگین f1 (N=10) واریانس 0.4571 0.4410 0.3585 0.3925 0 0 0 0 1.4056 1.1466 1.3490 1.3178 0 0 0 0.1088 میانگین f2 (N=5) واریانس 0.5644 0.5718 0.6884 0.7873 0 0 0 0.3850 7.8199 4.4232 4.3928 3.4115 0 0 0 0.3901 میانگین f2 (N=10) واریانس 1.6377 1.5836 1.3886 1.4872 0 0 0 0.3050 3.1058 0.2005 0.0694 0.1151 0 0 0 0 میانگین f3 (N=5) واریانس 1.5126 0.2285 0.0840 0.1550 0 0 0 0 22.0992 5.8505 2.4781 2.9068 0 0 0 0 میانگین f3 (N=10) 5.5794 1.8609 1.0280 1.1112 0 0 0 0 واریانس -2.0949e+3 -2.0933e+3 -2.0940e+3 - 2.0937e+3 - 1.5365e+3 -1.3412e+3 -1.8172e+3 - 1.6458e+3 میانگین f4 (N=5) واریانس 783.0502 1.3213e+3 655.1495 773.7160 5.1 0.2791 0.4455 2.1569 -4.1897e+3 -4.1890e+3 -4.1898e+3 - 4.1895e+3 - 2.0613e+3 -2.4097e+3 -3.3396e+3 - 2.9970e+3 میانگین f 4 (N=10) 1.5152e+3 1.2698e+3 1.1275e+3 0.3401 0.2094 0.9099 0.2472 1.21901e+ 3 واریانس 0.1806 0.1313 0.1120 0.2416 0 0 0 0 میانگین f5 (N=5) 0.1059 0.0795 0.1068 0.1436 0 0 0 0 واریانس 1.5112 1.2219 1.1651 1.3132 0 0 0 0 میانگین f5 (N=10) واریانس 0.4425 0.2381 0.2861 0.3122 0 0 0 0 خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 97 همانطور که در جدول (5 (دیده می شود، الگوریتم ترکیبی GA-CA به ازای همۀ مقادیرpm مینیمم گلوبال توابعf1 و f3 و f5 را به صورت دقیق پیدا کرده است. همچنین الگوریتم ترکیبی برای تابع f2 با 5=N و 10=N و به ازای مقادیر احتمال تقاطع 1pm.0 =و pm.0 =و 0pm =مینیمم گلوبال را به صورت دقیق پیدا کرده است. برای تابع f4 نیز الگوریتم ترکیبی نزدیکترین پاسخ را به مینیمم گلوبال به ازای 5pm.0 =و 9pm.0 =پیدا کرده است. 3 -3 -بررسی اثر تعداد تولید الگوریتم ژنتیک به منظور بررسی اثر تعداد تکرارهای Gmax بر کارایی الگوریتم های sGA و GA-CA در پیدا کردن مینیمم گلوبال، مطابق با جدول (6 (سه مقدار تولید Gmax متفاوت برای هر دو الگوریتم در نظر گرفته شده است. همچنین احتمال تقاطع در هر دو الگوریتم 8.0=pc و 5pm.0) =با توجه به بخش قبل) در نظر گرفته شده است و به منظور مقایسه صحیح میان الگوریتم ژنتیک و الگوریتم ترکیبی GA-CA و با توجه به دلایل ذکر شده در بخش قبل تعداد کروموزومهای ( قوانین) اولیه در الگوریتم ترکیبی GA-CA را  و تعداد کروموزوم های جمعیت اولیه MH  را در الگوریتم استاندارد sGA برابر در نظر گرفته ایم. همانطور که در جدول (6 (دیده می شود، الگوریتم ترکیبی GA-CA به ازای تمامی تکرارهای Gmax برای توابع f1 و f3 و f5 مینیمم گلوبال را به صورت دقیق پیدا کرده است و برای تابع f2 با 5=n و 10=n و به ازای100Gmax= و150Gmax= مینیمم گلوبال را به صورت دقیق پیدا کرده است و برای تابع f4 با 5=n و 10=n و به ازای 100Gmax =دقیقترین مینیمم گلوبال را پیداکرده است. الگوریتم استاندارد GA به ازای همۀ مقادیر Gmaxدر پیدا کردن مقدار مینیمم در مقایسه با الگوریتم ترکیبیGA-CA دارای خطای قابل توجهی است. در الگوریتم استاندارد GA هر چه تعداد تکرارها بیشتر شود، جوابها به مینیمم گلوبال نزدیکتر می شود. همچنین هر چه درجه توابع بیشتر می شود، الگوریتم استانداردsGA درپیدا کردن مینیمم گلوبال دچار خطای بیشتری می شود. 3 -4 -بررسی اثر تعداد کروموزومهای جمعیت اولیۀ الگوریتم ژنتیک جدول (7 (اثر تعداد کروموزوم های M جمعیت اولیه را بر پیدا کردن مینیمم توابع استاندارد نشان میدهد. به منظور مقایسۀ صحیح میان الگوریتم ژنتیک و الگوریتم ترکیبی GA-CA ،تعداد کروموزومهای (قوانین) اولیه در الگوریتم ترکیبی MHو تعداد کروموزومهای جمعیت را CA-GA اولیه را در الگوریتم استاندارد sGA برابر !Error که(Bookmark not defined. M M   M H است) در نظر گرفته و مقادیر  وpc را به ترتیب 30 و 8.0 انتخاب کرده ایم. همانطور که در این جدول دیده می شود، در مورد توابع f1 وf2 و f3 و f5 الگوریتم GA-CA به ازای همۀ مقادیر جمعیت اولیه کروموزومهای به مقدار مینیمم گلوبال تابع رسیده است و در حالت کلی الگوریتم استاندارد sGA به ازای همه مقادیرجمعیت اولیه M در پیدا کردن مقدار مینیمم در مقایسه با MH ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 98 الگوریتم ترکیبیGA-CA دارای خطای قابل توجهی است. همچنین هر چه درجه توابع بیشتر شود، الگوریتم استاندارد sGA در پیدا کردن مینیمم گلوبال دچار خطای بیشتری میشود. جدول (6 :(توابع استاندارد در 100 بار اجرای الگوریتم ترکیبی GA-CA .تعداد پارامتر احتمال تقاطع 8.0 و تعداد کروموزوم های جمعیت اولیه در الگوریتم ژنتیک 600 و در الگوریتم ترکیبیGA-CA 20 در نظر گرفته شده است. الگوریتم ترکیبی GA-CA الگوریتم ژنتیک استاندارد sGA توابع مورد بهینه سازی Gmax=50 Gmax=100 Gmax=150 Gmax=50 Gmax=100 Gmax=150 0.9246 0.3086 0.2870 8.8818e-16 8.8818e-16 8.8818e-16 میانگین f1 (N=5) 0.5251 0.1955 0.1811 0 0 0 واریانس 2.8697 1.7323 1.7199 8.8818e-16 8.8818e-16 8.8818e-16 میانگین f1 (N=10) 0.4387 0.3585 0.3405 0 0 0 واریانس 1.5895 1.3490 1.3099 0.3519 0 0 میانگین f2 (N=5) 0.8499 0.6884 0.5978 0.9007 0 0 واریانس 4.9478 4.3928 4.1256 0.5120 0 0 میانگین f2 (N=10) 1.5507 1.3886 1.1467 1.7231 0 0 واریانس 0.3301 0.0694 0.0510 0 0 0 میانگین f3 (N=5) 0.2956 0.0840 0.0750 0 0 0 واریانس 5.1724 2.4781 2.0999 0 0 0 میانگین f3 (N=10) 1.6710 1.0280 0.9679 0 0 0 واریانس -1.8918e+3 -1.9016e+3 -1.9587e+3 -2.0903e+3 -2.0943e+3 -2.0939e+3 میانگین f4 (N=5) 1.1215e+3 987.5072 900.5726 14.3626 1.1455 3.1263 واریانس -3.6577e+3 -3.8931e+3 -3.9921e+4 -4.1822e+3 -4.1883e+3 -4.1882e+3 میانگین f 4 (N=10) 1.3100e+3 1.1580e+3 1.1009e+3 15.2339 5.4099 3.1339 واریانس 0.2860 0.1341 0.9018 0 0 0 میانگین f5 (N=5) 0.1240 0.0574 0.0379 0 0 0 واریانس 1.2222 0.9578 0.8641 0 0 0 میانگین f5 (N=10) 0.1388 0.1328 0.1185 0 0 0 واریانس خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 99 این بدان معنی است که میزان صحت الگوریتم استانداردsG در پیدا کردن نقاط بهینه به درجۀ پیچیدگی تابع مورد بهینه سازی وابسته است؛ از طرفی با افزایش تعداد کروموزمهای جمعیت اولیه کارایی الگوریتم استانداردsGA و الگوریتم ترکیبی GA-CA در یافتن نقطه مینیمم بهینه بیشتر می شود. جدول (7 :(مقایسه کارایی الگوریتم sGA و الگوریتم ترکیبی GA-CA به ازای سه مقدار مختلف جمعیت اولیه کروموزومها الگوریتم ترکیبیGA-CA الگوریتم ژنتیک استاندارد sGA توابع مورد بهینه سازی  150 M H  100 M H  20 M= M H M=60 M=3000 4500 0.3086 0.0516 0.0497 8.8818e-16 8.8818e-16 8.8818e-16 میانگین f1 (N=5) واریانس 0.1955 0.0285 0.0260 0 0 0 1.7323 0.4106 0.2328 8.8818e-16 8.8818e-16 8.8818e-16 میانگین f1 (N=10) 0.3585 0.1982 0.1105 0 0 0 واریانس 1.3490 0.8433 0.8111 0 0 0 میانگین f2 (N=5) واریانس 0.6884 0.4673 0.0391 0 0 0 4.3928 3.7331 3.1225 0 0 0 میانگین f2 (N=10) واریانس 1.3886 1.3624 1.3234 0 0 0 0.0694 0.0033 0.0031 0 0 0 میانگین f3 (N=5) 0.0840 0.0030 0.0015 0 0 0 واریانس 2.4781 0.1985 0.1890 0 0 0 میانگین f3 (N=10) واریانس 1.0280 0.1794 0.1601 0 0 0 -2.0943e+3 2.0948e+3 2.0949e+3 - 3.5319e+3 - 1.9475e+3 -1.8616e+3 میانگین f4 (N=5) واریانس 987.5072 1.0654e+3 1.0652e+3 0.2455 0.0853 0.0741 -4.1883e+3 -4.1894e+3 -4.1896e+3 - 3.7328e+3 - 2.7416e+3 -2.4931e+3 میانگین f 4 (N=10) 1.1580e+3 1.3377e+3 1.1968e+3 1.1099 0.9631 0.5631 واریانس 0.1341 0.0364 0.0228 0 0 0 میانگین f5 (N=5) واریانس 0.0574 0.0169 0.0154 0 0 0 0.9578 0.4256 0.3981 0 0 0 میانگین f5 (N=10) واریانس 0.1328 0.1860 0.1589 0 0 0 ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 100 3-5 -مقایسه سرعت همگرایی دو الگوریتم sGA و CA-GA برای مقایسۀ سرعت همگرایی الگوریتم های sGA و GA-CA به بهترین مقدار برازندگی (مینیمم گلوبال تابع)، دو الگوریتم به منظور پیدا کردن مینمم گلوبال تابع Ackley) به عنوان نمونهای شناخته شده از توابع مورد بحث در بهینهسازی) استفاده شده است و تغییرات میانگین مقادیر برازندگی و بهترین مقدار برازندگی کروموزمها در 50 بار تولید در شکل (2 (ترسیم شدهاند. لازم به ذکر است آنچه در نهایت برای خروجی الگوریتمهای GA-CA و sGA به عنوان مینیمم تابع Ackley پیشنهاد میگردد، بهترین مقدار برازندگی مجموعه کروموزومها پس از 50 بار تولید میباشد که با نقاط پررنگ (مشکی) در نمودارهای شکل (1( نشان داده شده اند. (الف) (ب) شکل (2 :(تغییرات مقادیر بهترین برازندگی کروموزوم ها در 50 بار تولید به منظور پیدا کردن مینیمم گلوبال تابع Ackley . نقاط کمرنگ بیانگر میانگین مقادیر برازندگی در مجموعه کروموزوم ها در هر بار تولید و نقاط پررنگ بهترین برازندگی در میان همۀ کروموزوم ها در هر بار تولید است. الف) تغییرات مقادیر برازندگی در کروموزوم های الگوریتم GA-CA ب) تغییرات مقادیر برازندگی در کروموزوم های الگوریتم استانداردsGA همانطور که در قسمت الف شکل (2 (مشاهده میشود، الگوریتم ترکیبی GA-CA در هشتمین تولید به مینیمم گلوبال تابع دست مییابد، اما بهترین مقدار برازندگی در الگوریتم استاندارد sGA) قسمت ب شکل (2 (در 50 بار تولید هنوز به مینیمم گلوبال دست نیافته است. این آزمایش به همراه سایر آزمایشات (پس از 100 بار اجرای الگوریتم) نشان داد به طور متوسط سرعت همگرایی الگوریتم ترکیبی GA-CA برای یافتن مینیمم گلوبال تابع Ackleyدر حدود 5 برابر بیشتر از سرعت همگرایی الگوریتم استاندارد خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 101 sGA میباشد. برای سایر توابع مورد بهینهسازی نیز نتایج مشابه استخراج گردید. 3-6 -بررسی اثر حساسیت به شرط اولیه در الگوریتم ترکیبیGA-CA شرایط اولیه یکی از مهمترین بخشهای مربوط به ماشین خودکار سلولی است. در این بخش هدف این است تا اثر تغییر در شرایط اولیه ماشین خودکار سلولی بر میزان کارایی الگوریتم ترکیبیGA-CA در پیدا کردن مینیمم گلوبال تابع مورد بهینهسازی بررسی شود. به همین منظور چهار شرط اولیه بر اساس محدودة مجاز متغیرهای توابع مورد بهینه سازی [ , ] L R i i و x x مطابق با روابط 7 و 8 برای ماشین خودکار سلولی در نظر گرفته شده اند. میانگین و واریانس بهترین مقادیر برازندگی مربوط به الگوریتم GA-CA با چهار مقدار مختلف شرط اولیه برای ماشین خودکار سلولی و 100 بار تکرار الگوریتم در جداول (8،9،10،11و12 (قابل مشاهده است. لازم به ذکر است اولین شرط اولیۀ ௅௜ پیشنهادی براساس کران پایین ݔ ، دومین شرط ோ ௜اولیه براساس کران بالای ݔ ، سومین شرط اولیه به صورت رندم و چهارمین شرط اولیه در نزدیکی نقطۀ مینیم گلوبال واقعی تابع مورد بهینه سازی (به عنوان مثال شرط اولیه 5/0برای توابع نظر در ) f4 تابع برای 417.1811 و f1 , f2, f3, f5 گرفته شده است. جدول (8 :(کارایی الگوریتم ترکیبی GA-CA در پیدا کردن مینیمم تابع (5=n (f1 i مقادیر دهدهی x های مورد استفاده در شرط اولیه الگوریتم ترکیبی واریانس میانگین GA-CA xi(0) = -32.7680, i=1,2,..,10 8.8818e-016 0 xi(0) = 32.7680, i=1,2,..,10 8.8818e-016 0 xi(0) = -27.0512, i=1,2,..,10 8.8818e-016 0 xi(0) = 0.5, i=1,2,..,10 8.8818e-016 0 جدول (9 :(کارایی الگوریتم ترکیبی GA-CA در پیدا کردن مینیمم تابع (5=n (f2 i مقادیر دهدهی x های مورد استفاده در شرط اولیه الگوریتم ترکیبی واریانس میانگین GA-CA xi(0) = -2.048 , i=1,2,..,10 0 0 xi(0) = 2.048 , i=1,2,..,10 0 0 xi(0) = -1.640 , i=1,2,..,10 0 0 xi(0) = 0.5 , i=1,2,..,10 0 0 ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 102 جدول (10 :(کارایی الگوریتم ترکیبی GA-CA در پیدا کردن مینیمم تابع (5=n (f3 های مورد استفاده در شرط اولیه الگوریتم ترکیبی -CA i مقادیر دهدهی x GA واریانس میانگین xi(0) = -5.120 , i=1,2,..,10 0 0 xi(0) = 5.120 , i=1,2,..,10 0 0 xi(0) = -3.100 , i=1,2,..,10 0 0 xi(0) = 0.5 , i=1,2,..,10 0 0 جدول (11 :(کارایی الگوریتم ترکیبی GA-CA در پیدا کردن مینیمم تابع (5=n (f4 های مورد استفاده در شرط اولیه الگوریتم ترکیبی -CA i مقادیر دهدهی x GA میانگین واریانس xi(0) = -500, i=1,2,..,10 -2.0940e+3 2.1345 xi(0) = 500, i=1,2,..,10 -2.0943e+3 1.1099 xi(0) = -300.1792, i=1,2,..,10 -2.0947e+3 0.8141 xi(0)= 417.1811, i=1,2,..,10 -2.0948e+3 0.2798 جدول (12 :(کارایی الگوریتم ترکیبی GA-CA در پیدا کردن مینیمم تابع (5=n (f5 های مورد استفاده در شرط اولیه الگوریتم ترکیبی -CA i مقادیر دهدهی x GA میانگین واریانس xi(0) = -600, i=1,2,..,10 0 0 xi(0) = 600, i=1,2,..,10 0 0 xi(0) = -500.12, i=1,2,..,10 0 0 xi(0) = 0.5, i=1,2,..,10 0 0 همانطور که در جداول شماره (12و10 و9و8( قابل مشاهده است، مقادیر کارایی الگوریتم -CA GA) مقادیر میانگین و واریانس مینیمم های پیدا شده در 100 بار اجرای الگوریتم) مستقل از مقادیر اولیه است، اما جدول (10 (نشان می دهد که کارایی الگوریتم ترکیبی GA-CA به میزان بسیار ناچیزی وابسته به شرایط اولیه میباشد و بهترین کارایی، زمانی به دست میآید که شرط اولیه ماشین خودکار سلولی بر اساس نزدیکترین نقطه به مینیمم گلوبال واقعی تابع مورد بهینه سازی f4 در نظر گرفته شود؛ اگر چه آزمایشات دیگر نشان داد که بهتر است کران پایین ௅௜ݔ درشرط اولیه ماشین خودکار سلولی مورد استفاده قرار گیرد.  1  شکل (3 (اثرات دو شرط اولیه متفاوت(0  t( و ( 0) 2  t   ماشین خودکار سلولی را در پیدا کردن خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 103 مینیمم گلوبال تابع schwefel با 5 متغیر نشان میدهد. دو مقدار مختلف 500)=-0(xi و-=(0(xi 1792.300 به ترتیب در ساختار شرایط اولیه و به صورت ذیل مورد استفاده قرار گرفتهاند: ( ) 1 ( 1) 1    t NL n  , bin dec t NL n ( )... (111110100) (500) ( 1) 1      bin t t n L flt nN  ( )... ( )  (00000000000000) 00 (0) 6 1111110100 0000000000 0000 (0) 5 1111110100 0000000000 0000 (0) 4 1111110100 0000000000 0000 (0) 3 1111110100 0000000000 0000 (0) 2 1111110100 0000000000 0000 (0) 1 ( 0) 001111110100 0000000000 0000 1        x x x x x x   t   ( ) 1 ( 1) 1    t NL n  , bin dec t NL n ( )... (1100101100) (300) ( 1) 1      , bin dec t t n L flt nN  ( )... ( )  (11100000000000)  (1792) 00 (0) 6 1110010110011100000000000 (0) 5 1110010110011100000000000 (0) 4 1110010110011100000000000 (0) 3 1110010110011100000000000 (0) 2 1110010110011100000000000 (0) 1 ( 0) 001110010110011100000000000 2        x x x x x x   t   همانطور که در شکل (3 (قسمت الف دیده میشود، قانون شمارة ( 0) 1  t   ( 0) 2  t   ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 104 ( الف ) (ب)  1  شکل (3 :(مقایسه نتایج به دست آمده از قرار دادن دو شرط اولیه (0  t( ( 0) و 2  t   ماشین خودکار سلولی در پیدا کردن نقطه مینیم گلوبال تابع schwefel پنج متغیره. شکل های سمت چپ، نشان دهندة رشتۀ بیت تولید شده توسط ماشین خودکار سلولی در لحظه t است. در این شکلها مربعهای سفید معرف بیت 0 و مربعات سیاه معرف بیت 1 است. الف) شکل سمت راست تغییرات بهترین مقادیر برازندگی الگوریتم ژنتیک، شکل سمت چپ 30 رشته تولید شده ماشین خودکار سلولی با شرط اولیه توسط قانون شماره 2828770 پیدا شده توسط الگوریتم ژنتیک. ب) شکل سمت راست تغییرات مقادیر برازندگی الگوریتم ژنتیک، شکل سمت چپ 30 رشته تولید شده ماشین خودکار سلولی با شرط اولیه توسط قانون شماره 7862513 پیدا شده توسط الگوریتم ژنتیک. 2828770 با بهترین برازندگی3+2094e توسط الگوریتم ژنتیک در دهمین تولید (17=G (وسومین تکرار (3=t (ماشین خودکار سلولی پیدا شده است. همچنین در شکل (2 (قسمت ب، قانون شمارة 7862513 با بهترین مقدار برازندگی 3+2093e توسط الگوریتم ژنتیک در 105 امین تولید (105=G (و 12 امین تکرار (12=t (ماشین خودکار سلولی پیدا شده است. بنابراین ( 0) 1  t   ( 0) 2  t   خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 105 مینیممهای پیدا شده با استفاده از این دو شرط اولیه CA تقریباً برابر با مینیمم گلوبال واقعی تابع schwefel پنج متغیره یعنی مقدار3+2094eاست. لازم به ذکر است قوانین مشاهده شده در شکل، نمونه ای از قوانینی است که الگوریتم ژنتیک پبدا می کند. 4 -بحث و نتیجه گیری در این مقاله روشی جدید به منظور افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین خودکار سلولی یک بعدی پیشنهاد گردید و میزان کارایی و ویژگیهای الگوریتم ترکیبی GA-CA پیشنهاد شده با الگوریتم ژنتیک استاندارد sGA در حل مسالۀ بهینهسازی مورد ارزیابی و مقایسه قرار گرفت. آزمایشات نشان داد کارایی الگوریتم ژنتیک استاندارد sGA با افزایش درجه تابع مورد بهینه سازی افزایش مییابد؛ در صورتی که وابستگی الگوریتم ترکیبی GA-CA به درجه تابع، بسیار ناچیز است. نتایج به دست آمده نشان داد که به جز تابع schwefel ،در تمامی توابع کارایی الگوریتم ترکیبی GA-CA مستقل از شرط اولیۀCA می باشد و در مورد تابع schwefel نیز کارایی الگوریتم پیشنهادی وابستگی بسیار پایینی به شرط اولیۀ ماشین خودکار سلولی CA دارد و بهترین جواب، زمانی به دست میآید که شرط اولیه در نزدیکی نقطه مینیمم واقعی تابع مورد بهینهسازی قرار داشته باشد. البته در حالت کلی پیشنهاد میشود که شرط اولیه ماشین خودکار سلولی CA در الگوریتم ترکیبی GA-CA براساس کران پایین مجاز برای متغیرهای تابع مورد بهینهسازی تعیین شود. نتایج دیگر آزمایشات نشان داد که سرعت همگرایی الگوریتم ترکیبی GA-CA در رسیدن به مینیمم گلوبال واقعی تابع به وضوح بسیار بیشتر از الگوریتم ژنتیک استاندارد sGA است. همچنین دیگر نتایج نشان داد که انحراف معیار جوابهای به دست آمده از الگوریتم ترکیبی GA-CA در 100 بار اجرای این الگوریتم در اغلب موارد صفر و یا در حالت کلی بسیار کمتر از الگوریتم ژنتیک استاندارد میباشد که این نشاندهندة تکرارپذیری بهتر جوابهای الگوریتم ترکیبی GA-CA نسبت به الگوریتم استاندارد sGA است. دیگر نتایج نشان داد که نقش الگوریتم ژنتیک GA در الگوریتم ترکیبی GA-CA ،پیدا کردن بهترین قوانین برای ماشین خودکار سلولی CA است که بتوانند پاسخ مینیمم گلوبال تابع مورد بهینهسازی را تولید کنند. بنابراین میتوان جدولی از بهترین قوانین مربوط به CA را برای هر تابع مورد بهینه سازی تولید نمود. به طور کلی با توجه به نتایج به دست آمده میتوان گفت که الگوریتم ترکیبیGA-CA در بسیاری از موارد می تواند کارایی بهتری نسبت به الگوریتم ژنتیک استاندارد در مسائل بهینه سازی داشته باشد. به نظر می رسد که دلیل این امر آن است که این الگوریتم با بهرهگیری از تنوع زیاد قوانین محلی موجود میان سلولهای CA که توسط الگوریتم GA انتخاب میشوند، میتواند ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 106 جستجوی متنوع و قانونمندی را جهت دستیابی به پاسخ بهینه انجام دهد؛ در حالی که جستجوی الگوریتم استانداردsGA در فضای حل مسئله، مستقیماً بر اساس روشهای محدود و مبتنی بر تصادف انجام میشود. پیشنهاد میشود از الگوریتم ترکیبی پیشنهادی در این مقاله در مدلسازی برخی از مکانیزمهای طبیعی همچون فرآیند یادگیری در مغز انسان استفاده شود. همچنین از ویژگیهای خودسازماندهی و خودتولید کنندهای مبتنی بر قوانین محلی ماشین خودکار سلولی CA به منظور بهینه سازی برخی دیگر از الگوریتمهای بهینهسازی نظیر PSO نیز استفاده شود. ضمائم توابع مورد بهینه سازی استفاده شده در مقاله: (12)                   n i a i cx n n i i x n f x a b 1 cos( )) exp( 1 exp( 1 2 1 ( ) . exp . 1 نظر در a  20, b  0.2, c  2 رابطه این در که گرفته شده است. مینیمم این تابع صفر و در0 =xi کهn,…,1=i قرار دارد. (13) که مینیم این تابع صفر و در 1௜ = ݔ که .دارد قرار i=1,…,n   (14)     n i i x i f x n x 1 10cos(2 ) 2 ( ) 10 3  که مینیم این تابع صفر و در 0 =xi که .دارد قرار i=1,…,n    (15)    n i i x i f x x 1 ( ) sin( ) 4 که مینیم این تابع صفر و در 9687.420 =xi کهn,…,1=i قرار دارد. 1 (16) 1 cos 4000 1 1 ( ) 5 2               n  i i i x n i f x i x که مینیمم این تابع صفر و در 0 =xi که n,…,1=i قرار دارد. لازم به ذکر است نمودارهای سه بعدی هر یک از توابع شکل (3 (قابل مشاهده است. Ackley Rosenbrock Rastrigin خودکار سلولی یک بعدی افزایش کارایی الگوریتم ژنتیک با استفاده از ماشین 107 Schwefel Griewangk شکل (3 :(نمایش سه بعدی توابع استاندارد مورد بهینهسازی با دو متغیر x1 وx2

مراجع

1. Katsaras, Vlasis K. Koumousis and Christos P. “A Saw-Tooth Genetic Algorithm Combining the Effects of Variable Population Size and Reinitialization to Enhance Performance”. 1, s.l. : IEEE, FEBRUARY 2006, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, Vol. 10. doi:10.1109/TEVC.2005.860765. 2. Liu, Juan Cai, Zixing Liu, Jianqin. Hefei, “Premature Convergence in Genetic Algorithm :Analysis and Prevention Based on Chaos Operator.” P.R. China : Proceedings ofthe 3rd World Congress on Intelligent Control and Automation, 2000 , June 28-July 2. pp. 495–499. doi:10.1109/WCICA.2000.860016. 3. Ondrej Hrstkaa, Anna Kucerovab,. “Improvements of real coded genetic algorithms based on differential operators preventing premature convergence.” s.l. : Advances in Engineering Software, 2004, Vol. 35, pp. 237–246. doi:10.1016/S0965-9978(03)00113-3. 4. J. Andrea, P. Siarryb,T. Dognona. “An improvement of the standard genetic algorithm fighting premature convergence in continuous optimization.” s.l. : Advances in Engineering Software, 2001, Vol. 32, pp. 49-60. doi:10.1016/S0965-9978(00)00070-3. 5. Abu Bakar Md Sultan, Ramlan Mahmud, Muhammad Nasir Sulaiman. “Reducing Premature Convergence Problem through Numbers Structuring in Genetic Algorithm.” 4, s.l. : IJCSNS International Journal of Computer Science and Network Security, April 2007, Vol. 7. doi:10.1.1.130.5783. 6. Riccardo Caponetto, Member, IEEE, Luigi Fortuna, Stefano Fazzino, and Maria Gabriella Xibilia. “Chaotic Sequences to Improve the Performance of Evolutionary Algorithms.” 3, s.l. : IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, JUNE 2003, Vol. 7, pp. 289-304. doi: 10.1109/TEVC.2003.810069. 7. Wu, J. Cao Q. H. “A CELLULAR AUTOMATA BASED GENETIC ALGORITHM AND ITS APPLICATION IN MECHANICAL DESIGN OPTIMISATIONY.” s.l. : UKACC International Conference on CONTROL, 1998, September. pp. 1-4. doi: 10.1049/cp:19980467. 8. Yufa Xu “A Hybrid Optimization Method Based on Cellular Automata and Its aplication in SoftSensing Modeling.” 1, 2, Guochu Chen1, and Jinshou Yu2. Haikou, Hainan, China : ICNC '07 Proceedings of the Third International Conference on Natural Computation, 2007 , August. doi:10.1109/ICNC.2007.53. 9. Ilachinski, Andrew, “Cellular Automata, A discrete universe.” s.l.: World Scientific Publishing, 2001. p. 71. ISBN 981-02-4623-4. ی ـ مهندس ر طراحـی د ات ـ اوری اطلاع ـ ه فن ـ مجل 108 10. Neumann, John von. “The general and logical theory of automata.” Los Alamos : John Wiley & Sons, New York, 1951. pp. 1-31. 11. wolfram, Stephen. “Statistical mechanics of cellular automata.” 2, July 1983, Reviews of Modern Physics, Vol. 55. doi:10.1103/RevModPhys.55.601. 12. Kesslcr, D.A., H.Lavine and W.N.Reynolds. “Coupled-map lattice model for crystal growth.” 1990, Phys. Rev, Vol. 42. doi:10.1103/PhysRevA.42.6125. 13. M. Chahoud1, D. Fehly, H. -H. Wehmann, and A. Schlachetzki. “Cellular-automata -based simulation of anisotropic crystal growth.” 4, December 2000, Journal of Crystal Growth, Vol. 220, pp. 471-479 . doi:10.1016/S0022-0248(00)00902-7. 14. Ch. Mizasa, G.Ch. Sirakoulisa, V. Mardirisa, I. Karafyllidisa, N. Glykosb and R. Sandaltzopoulos. “Reconstruction of DNA sequences using genetic algorithms and cellular automata: Towards mutation prediction?” 1, April 2008, Biosystems, Vol. 92, pp. 61-68 . doi: 10.1016/j.biosystems.2007.12.002. 15. G. Ch. Sirakoulisa, I. Karafyllidis , b, Ch. Mizasa, V. Mardirisa, A. Thanailakisb and Ph. Tsalidesb. “A cellular automaton model for the study of DNA sequence evolution.” 5, September 2003, Computers in Biology and Medicine , Vol. 33, pp. 439-453. doi:10.1016/S0010- 4825(03)00017-9 I. 16. Langton, Christopher. “Studying Artificial Life With Cellular Automata.” 1-3, s.l. : 22, OctoberNovember 1986, Physica D: Nonlinear Phenomena, pp. 120-149. doi:10.1016/0167- 2789(86)90237-X. 17. L. Hernández Encinasa, S. Hoya Whiteb, A. Martín del Reyc, and G. Rodríguez ánchezd. “Modelling forest fire spread using hexagonal cellular Automata.” 6, June 23, 2007, Applied Mathematical Modelling, Vol. 31, pp. 1213-1227. doi:10.1016/j.apm.2006.04.001. 18. Ying Zhenga, Bin Jia, a, Xin-Gang Lia and Nuo Zhua. “Evacuation dynamics with fire spreading based on cellular automaton.” 18-19, September 15, 2011, Physica A: Statistical Mechanics and its Applications , Vol. 390, pp. 3147-3156 . doi:10.1016/j.physa.2011.04.011. 19. Acedoa, L. “A cellular automaton model for collective neural dynamics.” 5-6, September 2009, Mathematical and Computer Modelling, Vol. 50, pp. 717-725. doi:10.1016/j.mcm.2008.12.018. 20. Lev Naumova, Alfons Hoekstraa, and Peter Sloot. “Cellular automata models of tumour natural shrinkage.” 12, June 15 , 2011, Physica A: Statistical Mechanics and its Applications, Vol. 390, pp. 2283-2290 . doi:10.1016/j.physa.2011.02.006. 21. P. Gerlee, a, and A.R.A. Andersona. “An evolutionary hybrid cellular automaton model of solid tumour growth.” 4, June 21 , 2007, Journal of Theoretical Biology, Vol. 246, pp. 583-603 . doi:10.1016/j.jtbi.2007.01.027. 22. P. Gerlee, a, and A.R.A. Andersona. “A hybrid cellular automaton model of clonal evolution in cancer: The emergence of the glycolytic phenotype.” 4, February 21, 2008, Journal of Theoretical Biology , Vol. 250, pp. 705-722 . doi:10.1016/j.jtbi.2007.10.038. 23. Zykov V., Mytilinaios E., Adams B., Lipson H. “Self-reproducing machines.” 7038, 2005, Nature , Vol. 435, pp. 163-164. doi:10.1038/435163a. 24. JH, Holland. “Adaptation in natural and artificial systems.” Internal report. Ann Arbor,MI : University of Michigan, 1975. 25. P.M. Mateo, I. Alberto. “A mutation operator based on a Pareto ranking for multi-objective evolutionary algorithms.” s.l. : J Heuristics, 14 January 2011. DOI 10.1007/s10732-011-9156-4