جمعه 29 تیر 1397 | Friday 20 th of July 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
2-3-3- ارزیابی هزینۀ یک نمونۀ تخصیص حالت

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

تابع n می نامیم. که در صورت مجاور بودن صفر و در غیر این صورت مقدار یک را بر می گرداند. (توجه داشته باشید که می خواهیم به تخصیص حالت های بهتر هزینۀ کمتر تعلق گیرد.) نکتۀ مهم دیگری که باید به ان توجه شود این است که در یک تخصیص حالت نباید به دو حالت متمایز، کدهای یکسان تخصیص داده شود. در برنامۀ نوشته شده تابع a این مسأله را بررسی می کند، در صورت یکسان بودن مقدار صفر و در غیر این صورت یک عدد صحیح بزرگتر از صفر را بر می گرداند. تابع هزینه باید طوری تریف شود که برای اینگونه تخصیص حالت ها هزینۀ بالایی در نظر بگیرد. انقدر که ناکارامدی انها به وضوح دیده شود.

    همانطور که ملاحظه می کنید تابع هزینه 3 هدف را باید باهم در نظر بگیرد. باتوجه به رهیافت الگوریتم

1ژنتیک چند منظوره[1]، برای هر هدف وزنی قرار می دهیم.  هر زمان که قانون اول شکسته شود، تابع هزینه 2 واحد جریمه و هر گاه که قانون اول شکسته شود 1 واحد جریمه برای ان تخصیص حالت در نظر می گیرد. به طور کلی تابع هزینه از رابطۀ بدست می اید. جریمه را تابعی از تعداد حالت های ماشین تعریف کرده ایم:

با توجه به تابع fitness()[7]،  ماشین حالت جدول()، با تخصیص حالت زیر میزان هزینۀ ان 13 میباشد.

  

(2-8)

و با تخصیص حالت زیر میزان هزینۀ ان به 10 کاهش یافته است.

     

همانطور که در 2 مدار شکل(2-5) و (2-7) مشاهده می شود، با تخصیص حالت دوم که هزینۀ کمتری دارد، سبب شد که بخش ترکیبی مدار ساده تر شود. به طور کلی هدف الگوریتم ژنتیک، پیدا کردن تخصیص حالتی است که هزینۀ ان مینیمم شود. در واقع تخصیص حالت با هزینۀ صفر تمام قوانین مجاورتی را رعایت می کند. البته چنین تخصیص حالتی همیشه وجود ندارد. 

 

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26