مطالب وبلاگ

مراحل اجرای الگوریتم ژنتیک

به طور کلی نمودار ذیل، مراحل اجرای الگوریتم ژنتیکی را نمایش میدهد:

ga-shams

حال با توجه به نمودار گردش کار، مراحل کار الگوریتم را به این شکل بیان می‌کنیم:

1. با توجه به نوع مسئله و ساختار پاسخ‌های قابل قبول برای آن، ساختار کروموزومها را مشخص می‌سازیم. معمولاً یک راه‌حل مسئله، به صورت لیستی از متغیرهای مسئله نشان داده می‌شود که در اینجا نیز می‌توان آن را به صورت یک آرایه عددی نمایش داد.

2. تابع ارزیابی (Fitness function) مناسبی جهت ارزیابی کروموزومها (پاسخ‌ها) طراحی می‌کنیم. این مرحله اهمیت بسیار زیادی دارد، چرا که اگر نتوان تابعی مناسب جهت ارزیابی کروموزومهای تولید شده در نسلهای مختلف طراحی نمود، به هیچ وجه نمی‌توان مسئله مور نظر را با استفاده از الگوریتم ژنتیک حل کرد.

3. مقادیر پارامترهای اولیه الگوریتم را با توجه به صورت مسئله تعیین می‌کنیم. مهمترین پارامترهای مورد استفاده عبارتند از، اندازه جمعیت اولیه (N)، احتمالات مربوط به انتخاب (P­S)، ترکیب (PC)، جهش (PM)، ابقاء (PR) و همگرایی (PCN)، نوع انتخاب و نوع عملگرهای ترکیب و جهش.

4. یک جمعیت تصادفی با N کروموزوم تولید می‌شود. N اندازه جمعیت یا تعداد اعضای نسل آغازین بوده و هر کروموزوم نماینده یک جواب برای مساله است.

5. با استفاده از تابع ارزیابی، کیفیت تمام کروموزومهای این نسل را محاسبه و ذخیره می‌نماییم.

6. با توجه به مقدار کمیت درصد انتخاب (P­S)، جفت کروموزومهایی را به عنوان والدها انتخاب می‌کنیم. روند انتخاب والدها با استفاده از مقادیر ذخیره شده تابع ارزیابی انجام می‌گیرد.

7. هر جفت از والدها، با توجه به مقدار احتمال ترکیب (PC)، با یکدیگر ترکیب شده و یک یا دو کروموزوم فرزند تولید می‌کنند.

8. هر کروموزوم فرزند، با توجه به مقدار احتمال جهش (PM)، جهش می‌یابد.

9. با توجه مقدار احتمال ابقاء (PR)، تعدادی از فرزندان برای جایگزین شدن در نسل جدید انتخاب شده و مابقی نسل جدید از کروموزومهای نسل قبلی انتخاب می‌گردند، سپس نسل جدید به جای نسل قبلی در برنامه جایگزین می‌شود.

10. شرط توقف و خاتمه الگوریتم و همگرایی کروموزومها به پاسخ بهینه، بررسی می‌گردد. در صورتی که شرط توقف برقرار نشده باشد، اجرای الگوریتم را از مرحله 5 از سر می‌گیریم، در غیر این صورت بهترین کروموزوم نسل فعلی به عنوان پاسخ نهایی انتخاب شده و الگوریتم خاتمه می‌یابد.


مزایا و معایب الگوریتم ژنتیک

از مزایای GA در مقایسه با دیگر روشهای جستجو می‌توان به این موارد اشاره نمود:

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

با وجود تمام مزایا، مهمترین مشکل GA بالا بودن هزینه اجرایی آن است. چرا که معمولاً برای حل مسائل، نیاز به نگهداری چندصد کروموزوم در حافظه و اجرای الگوریتم تا چندهزار نسل خواهد بود. البته باید به خاطر داشت که GA یک الگوریتم متاهیوریستیک بوده و مدت زمان مورد نیاز برای اجرای آن در مقایسه با روشهای سیستماتیک، خیلی کمتر و بهینه‌تر است.

کاربرد اصلی الگوریتم‌های ژنتیک، حل مسائل بهینه‌سازی است، اما در واقع از این الگوریتم‌ها می‌توان در حل بهینه هر نوع مسئله‌ای که در فضای GA قابل پیاده‌سازی باشد استفاده نمود.

به عنوان مثال:

  • حل مسائل تصمیم‌گیری چند متغیره (Multi-objective problems).
  • الگوریتم‌های مسیریابی (Routing).
  • انواع مسائل مربوط به برنامه‌ریزی و زمانبندی (Scheduling).
  • انواع مسائل بسته‌بندی و تقسیم‌بندی (Partitioning) بهینه.
  • آموزش شبکه‌های عصبی مصنوعی (Artificial Neural Networks) و سیستمهای فازی (Fuzzy systems).
  • بهینه‌سازی طراحی مدارات الکترونیکی (VLSI).
  • بهینه‌سازی ساختارها و ترکیبات شیمیایی.
  • اجرای موازی الگوریتم بر روی سیستمهای چند پردازنده یا توزیع شده.
  • نرم‌افزارهای شناسایی و تشخیص الگو (Pattern recognition).
  • انواع الگوریتم‌های مورد استفاده در صنعت رباتیک.
  • دسته‌بندی (Classification) داده‌ها، داده‌کاوی (Datamining)  و یادگیری ماشین (Machine learning).
  • الگوریتم‌های بکار رفته در انواع بازی‌های کامپیوتری.
  • برخی از الگوریتم‌های پردازش تصاویر (Image processing).
  • انواع محاسبات عددی و روشهای تخمین توابع.
  • سیستمهای شبیه‌سازی حیات مصنوعی (Artificial life).
  • ساخت سیستمهای هوشمند تولید برنامه‌ تکاملی.

چیدمان خودکار کدها در Notepad++

تصور میکنم بتوان ادعا کرد که غیر ممکن است یک برنامه نویس نسبتا با تجربه، با برنامه Npp یا Notepad++ آشنا نباشد. این برنامه که تقریبا از سال 2010 به عنوان یک پروژه منبع باز ارائه شده، در واقع یک text editor و syntax highlighter سریع و ساده است.

npp

اگر بخواهیم مهمترین ویژگی های این ابزار را از زمان پیدایش آن تا کنون نام ببریم، میتوان به موارد زیر اشاره کرد:

  • فرمت و رنگ آمیزی زیبا و مناسب کدها برای خوانش بهتر و همینطور امکانات مناسب جهت چاپ آنها.
  • محیط multitab و امکان کار همزمان با فایلهای مختلف.
  • پشتیبانی عالی از عبارات باقاعده (RegEx) در Search and Replace.
  • امکان توسعه برنامه با استفاده از plugin های کاربردی.

یکی از قابلیتهایی که تا مدتها فقدان آن در این ادیتور محبوب احساس میشد، این بود که علاوه بر رنگ آمیزی و syntax highlight امکان format و کردن auto indentation هم موجود باشد.

در حال حاضر این فابلیت با استفاده از پلاگین NppAstyle برای زبانهای خانواده Java فراهم شده است. جهت استفاده از این پلاگین به آدرس پروژه آن https://code.google.com/p/nppastyle مراجعه نمایید.


چگونه از توابع مخرب یا destructor در Java استفاده کنیم

توابع مخرب یا destructor کاربرد زیادی در مدیریت حافظه برنامه های نوشته شده در C++ دارند. عموما در مورد کلاسهای طراحی شده، با استفاده از این متد به آزاد سازی حافظه پرداخته میشود.

javalogo

اما در زبانی مانند جاوا که مدیریت حافظه در اختیار ماشین مجازی میباشد، استفاده از این تابع چندان منطقی نیست، با این حال امکان پیاده سازی آن با استفاده از تابع finalize فراهم شده است.

برای انجام این کار در کلاس مربوطه یک تابع به نام finalize پیاده سازی گشته و سیستم Garbage Collector در زمان اتمام استفاده از کلاس و آزاد سازی تمام ارجاعات آن، تابه finalize را فراخوانی مینماید.

از آنجا که زمان عملکرد Grabage Collector نا مشخص است، با استفاده از دستورات gc و runFinalization میتوان ماشین مجازی را ملزم به آزاد سازی حافظه (جمع آوری زباله ها از حافظه) نمود.

مثال زیر نحوه انجام این کار را نشان میدهد:

import java.util.ArrayList;

public class Samples  {
    public static void main(String[] args){
        long mem = Runtime.getRuntime().freeMemory();

        SampleClass c1 = new SampleClass();
        SampleClass c2 = new SampleClass();
        SampleClass c3 = new SampleClass();

        System.out.println(String.format("Used memory: %d KB", (mem - Runtime.getRuntime().freeMemory())/1024));
        mem = Runtime.getRuntime().freeMemory();

        c1 = c2 = c3 = null;

        System.gc();
        System.runFinalization();

        System.out.println(String.format("Released memory: %d KB", (Runtime.getRuntime().freeMemory() - mem)/1024));
    }
}

class SampleClass {
    private ArrayList<Double> _obj;

    public SampleClass() {
        _obj = new ArrayList<Double>();
        for (int i=0; i<1000000; i++)
            _obj.add(Math.random());

        System.out.println("Created");
    }

    public void finalize() {
        _obj.clear();
        _obj = null;
        System.out.println("Finalized");
    }

}

خروجی احتمالی برنامه به این صورت است. بدیهیست که سیستم Garbage Collector هیچ تضمینی جهت مصرف یا آزاد سازی دقیق میزان حافظه ندارد.

Created
Created
Created
Used memory: 62354 KB
Finalized
Finalized
Finalized
Released memory: 11123 KB

چگونه از انبوه ایمیل‌های Gmail لیست مخاطبین ایجاد کنیم

حتما موافقید که در حال حاضر Gmail یکی از بهترین و قوی ترین سرویس های پست الکترونیکی رایگان است. همچنین محبوبیت آن در بین کاربران ایرانی مدتهاست که از رقیب خود، یعنی Yahoo، پیش افتاده است.

gmail-account

اما در این بین، سیاستهای شرکت گوگل مبنی بر ترغیب کاربران به استفاده از نسخه های تجاری یا خرید دسترسی و اکانت های پولی، گاهی باعث بوجود آمدن مشکلاتی میشود که به ساده قابل حل نیستند.

به عنوان مثال یکی از امکاناتی که سرویس Gmail باید داشته باشد، پردازش گروهی ایمیلهای دریافت شده برای اعمالی مانند Forward یا ذخیره سازی است.

مورد دیگر که مشکل اصلی مورد بحث در این مطلب می باشد، امکان گروه بندی مخاطبین یا فرستندگان ایمیلها بر اساس نوع متن یا عنوان ایمیل آنهاست.

در حال حاضر امکانات بخش Contacts گوگل به صورت موردی و یکی یکی قابل انجام است. یعنی تنها امکان اضافه کردن یک پست الکترونیک به صورت منفرد به عنوان مخاطب یا به یک گروه مخاطبین (Contact Groups) وجود دارد.
(ادامه مطلب…)



  • .
    Copyright (c) 2010 www.mshams.ir