همه چیز در باره الگوریتم تخمین توزیع – متن آموزشی کامل، دانلود رایگان

“الگوریتم تخمین توزیع مفهوم جدیدی در زمینه محاسبات تکاملی  است و با این ایده به وجود آمده است تا با ساخت یک مدل احتمالی از جمعیت مورد بررسی به حفظ بلوک‌های ساختاری  با ارزش در نسل‌های متوالی بپردازد. تحقیقات روزافزونی در این زمینه در حال پیگیری است و گونه‌های متفاوتی از این الگوریتم توسط محققان دانشگاه‌های مختلف ارائه شده‌است. برخی از محققین از نام‌هایی همچون ساختار مدل احتمالی الگوریتم‌های ژنتیک (PMBGAs) یا الگوریتم‌های تخمین چگالی تکرار (IDEAs)  برای توصیف این الگوریتم استفاده می‌کنند، اما همه این اسامی به مفهوم واحدی اشاره دارند. این الگوریتم‌ها بر اصول ژنتیکی زیادی متکی نیستند و بجای آن در هر نسل، مدل احتمالی صریحی از توزیع افراد خوب برگزیده شده در فضای جستجو می‌سازند. گام مدل-نمونه در EDA را می‌توان چیزی شبیه عمل crossover با چندین والد تصور کرد. نقطه قوت یا ضعف یک EDA ویژه به طور عمده توسط همین مدل احتمالی تعیین می‌گردد.”
آنچه خواندید، مقدمه فصل اول یکی از جامعترین متون فارسی در زمینه محاسبات تکاملی است که به بررسی الگوریتم های تخمین توزیع می پردازد. این متن ارزشمند را جناب آقای محمد خجسته فرد در ‫‫ﮔﺮوه ﻫﻮش ﻣﺼﻨﻮﻋﯽ‬ داﻧﺸﮑﺪه ﻣﻬﻨﺪﺳﯽ ﺑﺮق و ﮐﺎﻣﭙﯿﻮﺗﺮ‬ دانشگاه صنعتی اصفهان تهیه کرده اند و جهت استفاده سایر علاقه مندان، آن را جهت انتشار در اختیار وبسایت محاسبات تکاملی قرار داده اند. اگر به این حوزه مهم از هوش محاسباتی و محاسبات تکاملی علاقه مند هستید، این پست را از دست ندهید. در انتهای پست، فایل pdf متن کامل این نوشتار ارزشمند و جامع جهت دانلود در اختیار قرار داده شده است. در ادامه خلاصه ای از فصول مختلف این کار باارزش را می بینیم.

فهــرست مطالب
  1. فصل اول: مقدمه
    1. شرح مساله پژوهشی
    2. پيشينه و تاريخچه
    3. اهداف پژوهش
    4. اهميت و ارزش این پژوهش
    5. کاربرد نتايج پژوهش
    6. روش پژوهش
    7. ساختار پژوهش
  2. فصل دوم: مدل کلی الگوریتم تخمین توزیع
    1. مقدمه
    2. الگوریتم تخمین توزیع (EDA)
    3. معرفی نمادهای مورد استفاده
    4. ارائه یک مثال
    5. معرفی مراکز تحقیقاتی
  3. فصل سوم: مدل یک متغیره
    1. مقدمه
    2. شرح مدل یک متغیره
    3. الگوریتم جمعیتی بر اساس یادگیری افزایشی
    4. الگوریتم توزیع کناری یک متغیره
    5. الگوریتم ژنتیک متراکم
    6. موارد کاربرد و نتیجه گیری
  4. فصل چهارم: مدل دو متغیره
    1. مقدمه
    2. شرح مدل دو متغیره
    3. الگوریتم بیشینه سازی اطلاعات دوطرفه برای خوشه بندی ورودی
    4. الگوریتم ترکیب بهینه‌سازها با درخت‌های اطلاعات دوطرفه
    5. الگوریتم توزیع کناری دو متغیره
  5. فصل پنجم: مدل چند متغیره
    1. مقدمه
    2. شرح مدل چند متغیره
    3. الگوریتم ژنتیک متراکم توسعه‌یافته
    4. الگوریتم توزیع فاکتورگیری شده
    5. الگوریتم بهینه‌سازی بیزی
    6. الگوریتم یادگیری توزیع فاکتورگیری شده
    7. الگوریتم تخمین شبکة بیزی
    8. یادگیری شبکة احتمالی
  6. فصل ششم: پیچیدگی محسباتی
    1. مقدمه
    2. الگوریتم تخمین توزیع با اندازه جمعیت نامحدود
    3. کران بالایی برای پیچیدگی زمانی همگرایی سراسری
    4. محاسبة زمان توقف همگرایی سراسری
    5. نتیجه گیری
  7. فصل هفتم: آزمایشات
    1. مقدمه
    2. مسالة حاصل جمع زیر مجموعه‌ها
    3. مسالة بیشترین یک
    4. مسالة n وزیر
    5. نتیجه گیری
  8. فصل هشتم: الگوریتم‌های تخمین توزیع و یادگیری ماشین
    1. مقدمه
    2. کاربرد الگوریتم تخمین توزیع در یادگیری ماشین
    3. پیش زمینة یادگیری ماشین
    4. الگوریتم ID3
    5. ترکیب یادگیری استقرایی و یادگیری آماری در الگوریتم SI3E
    6. استخراج دانش از جمعیت با استفاده از ID3
    7. نقش PBIL
    8. مکان‌های ثابت و تشکیل مجموعة مثال‌ها
    9. الگوریتم SI3E و نحوة تنظیماتش
  9. مراجع
فصل اول: مقدمه
1-1 شرح مساله پژوهشی
الگوریتم تخمین توزیع  مفهوم جدیدی در زمینه محاسبات تکاملی  است و با این ایده به وجود آمده است تا با ساخت یک مدل احتمالی از جمعیت مورد بررسی به حفظ بلوک‌های ساختاری  با ارزش در نسل‌های متوالی بپردازد. تحقیقات روزافزونی در این زمینه در حال پیگیری است و گونه‌های متفاوتی از این الگوریتم توسط محققان دانشگاه‌های مختلف ارائه شده‌است. برخی از محققین از نام‌هایی همچون ساختار مدل احتمالی الگوریتم‌های ژنتیک (PMBGAs)  یا  الگوریتم‌های تخمین چگالی تکرار (IDEAs)  برای توصیف این الگوریتم استفاده می‌کنند، اما همه این اسامی به مفهوم واحدی اشاره دارند. این الگوریتم‌ها بر اصول ژنتیکی زیادی متکی نیستند و بجای آن در هر نسل، مدل احتمالی صریحی از توزیع افراد خوب برگزیده شده در فضای جستجو می‌سازند. گام مدل-نمونه در EDA را می‌توان چیزی شبیه عمل crossover با چندین والد تصور کرد. نقطه قوت یا ضعف یک EDA ویژه به طور عمده، توسط همین مدل احتمالی تعیین می‌گردد.ادامه دارد … ادامه را در فایل pdf انتهای پست ببینید.

فصل دوم: مدل کلی الگوریتم تخمین توزیع
2-1 مقدمه
الگوریتم ژنتیک کلاسیک، برای یافتن جواب مساله ابتدا جمعیتی از جوابهای اولیه بعضاً تصادفی را ایجاد می‌کند (اندازه جمعیت اصلی یا نسل فعلی را µ در نظر می‌گیریم) سپس در نسل‌های متوالی این الگوریتم تکرار شد و در هر نسل عملگر‌های ژنتیکی با دستکاری روی جمعیت اصلی به تولید جمعیت فرزندان  (اندازه جمعیت فرزندان جدید را λ در نظر می‌گیریم) می‌پردازد. در انتهای هر نسل، افراد منتخب از بین فرزندان وارد جمعیت اصلی شده و جایگزین افرادی که کمتر مفید هستند، می‌شوند. این الگوریتم در زیر آمده است.
شبه کد 1- الگوریتم ژنتیک کلاسیک
BEGIN
Generate initial population of size µ.
Evaluate each individual.
While (Termination candidate is not satisfied)
1.    Select parents;
2.    Recombine pairs of parents; /* Recombination rate */
3.    Mutate the resulting offspring; /* Mutation rate */
4.    Evaluate each new offspring; /* Now we have λ offsprings */
5.    Select individual for the next generation;
END
این الگوریتم را می‌توان با شکل 2.1 تطبیق داد.
شکل2.1: شمای کلی الگوریتم ژنتیک
در اين فصل سعی بر آن است که شرح کلی از فرم توسعه یافته این حالت کلاسیک به نام الگوریتم تخمین توزیع ارائه دهیم که در آن عملگر‌های ژنتیکی حذف شده‌اند.
2-2 الگوریتم تخمین توزیع  (EDA)
همانند الگوریتم ژنتیک کلاسیک تمام گونه‌های الگوریتم تخمین توزیع با یک جمعیت اولیه (با اندازه µ)کارشان را آغاز می‌کنند. سپس λ فرد از این µ فرد جمعیت اصلی را بر اساس معیار انتخابمان برمی‌گزینیم. تخمین توزیع به وسیله همین مجموعه افراد انتخاب شده محاسبه می‌شود (توزیع احتمال توأم افراد محاسبه می‌شود) و سپس با این تخمین از توزیع آنها، فرزندان را ایجاد کرده (نمونه برداری با استفاده از توزیع احتمال توأم تخمینی جمعیت) و آنها را جایگزین نسل والد می‌کنیم.
شبه کد 2- الگوریتم تخمین توزیع کلی
BEGIN
Generate initial population of size µ.
Evaluate each individual.
While (Termination candidate is not satisfied)
1.    Select λ promising individual where λ ≤  µ;
2.    Calculate joint probability distribution of selected individuals;
3.    Generate offspring according to the calculated probability distribution;
4.    Evaluate each new offspring;
5.    Replace offspring into main population based fitness rank;
END
در واقع می‌توان گفت که در شکل‌.1 بجای دو عمل جهش و تقاطع، واحد دیگری که وظیفه‌اش تخمین توزیع و نمونه برداری افراد جدید با استفاده از آن است قرار داده شده است. این الگوریتم در جدول 2 آورده شده‌است. این الگوریتم را می‌توان با شکل زیر تطبیق داد و با شکل 1.1 مقایسه نمود.
شکل2.2: شمای کلی الگوریتم تخمین توزیع
با نگاهی مختصر به دو شکل 2.1 و 2.2 می‌توان گفت که در شکل دوم ضمن حذف دو عملگر ژنتیکی جهش و تقاطع، مفهوم پدر نیز بعنوان نقش مستقیم در تولید فرزندان کمی کمرنگ‌تر به نظر می‌رسد. (زیرا این دفعه والدین مستقیماً فرزند تولید نمی‌کنند بلکه توزیع کلی والدین منتخب، منجر به تولید فرزندان می‌شود) در مدل دوم (شکل 2.2) با افزودن دو عمل تخمین و نمونه برداری به تولید جمعیت فرزندان پرداخته می‌شود.
به مرحله تخمین ، گام محاسبه  هم گفته می‌شود. در این مرحله با توجه به λ جواب امیدبخش  مدلی از توزیع جمعیت ساخته می‌شود که به نوعی گلوگاه کار هم در همین مرحله است و همانطور که بعداً خواهیم دید تفاوت در گونه‌های مختلف این الگوریتم ناشی از نوع ساختار مدلی است که آنها می‌سازند و البته یک نوع EDA خاص ممکن است اصلاً برای مساله ویژه‌ای مناسب نباشد. پس نباید تعجب کرد که بخش عمده این پژوهش هم معطوف به همین انواع مدل‌های احتمالی باشد.
هرچند در این روال هیچ کدام از عملگر‌های ژنتیکی پایه را نداشتیم اما به هر حال در برخی از گونه‌های الگوریتم تخمین توزیع عملگر‌هایی شبیه مجاز شمرده می‌شوند.
برخلاف الگوریتم‌های ژنتیکی ساده که به صورت ضمنی بر روی بلوک‌های ساختاری (BBs) پردازش انجام می‌دهند، پردازش‌های اینجا به طور کامل و صریح وابسته به استفاده از مدل احتمالی است. خوبی این مدل احتمالی فاکتور تعیین کننده‌ای در کارایی EDA به حساب می‌آید. هر چه دقت این مدل احتمالی بیشتر باشد الگوریتم به طور موثرتری از تخریب بلوک‌های ساختاری مهم اجتناب می‌ورزد.ادامه دارد … ادامه را در فایل pdf انتهای پست ببینید. 

فصل چهارم: مدل یک متغیره
4-1 مقدمه
وقتی قرار باشد مدلی از n متغیر که مشخص کننده نوع وابستگی آنها به یکدیگر است، را ارائه دهیم می‌توانیم این کار را با رسم گرافی نشان داد که رئوس متناظر متغیر‌های مساله است (یعنی n راس داریم) و یال‌هایش متناظر با وجود وابستگی بین دو متغیر است. البته باید حتماً این گراف دارای یال‌های جهت‌دار باشد زیرا وابستگی بین دو راس الزاماً دوطرفه نیست. راحتترین راه برای تصور مدل بین n متغیر یک گراف تهی است. یک گراف تهی دارای n راس و صفر یال است. در این حالت توزیع احتمال توأم آنها به وسیله ضرب احتمالات کناری n متغیر بدست می‌آید. بر طبق این ساختار تا کنون الگوریتم‌هایی مثل الگوریتم توزیع کناری یک متغیره یا UMDA ، جمعیتی براساس یادگیری افزایشی یا PBIL  و الگوریتم ژنتیک متراکم یا CGA  بکار گرفته شده‌اند. هر چند حیطه مسائلی که برای این الگوریتم‌ها وجود دارند خیلی وسیع نیست اما بعلت سادگی و کارایی خوبشان نسبت به الگوریتم ژنتیک کلاسیک در بسیاری موارد کاربرد دارند. در این فصل به شرح و انواع بسط این الگوریتم‌ها می‌پردازیم.

ادامه دارد … ادامه را در فایل pdf انتهای پست ببینید. 

فصل پنجم: مدل دو متغیره
5-1 مقدمه
همانطور در فصل پیش نشان دادیم در الگوریتم‌های تخمین توزیع عنصری که باعث تفاوت در کارایی الگوریتم می‌شود تا حدود زیادی به نوع مدلی که ما تعیین کرده‌ایم وابسته است. در فصل قبل در مورد مدل یک متغیره صحبت شد و نشان داده شد که این نوع از مدل‌ها در بسیاری از موارد کارایی چشمگیری در مقایسه با الگوریتم‌های ژنتیک کلاسیک ندارد و چه بسا از آنها بدتر‌هم معلوم است زیرا در مورد مسائل پیچیده که کارایی الگوریتم پائین می‌آید مدل یک متغیره با در نظر نگرفتن روابط بین متغیر‌ها عملاً تبدیل به الگوریتم ژنتیکی می‌شود که اولاً عنصر پراندگی و عملگر ایجاد پراکندگی را از دست داده و در رابطه با مسائل بهینه سازی، به احتمال زیاد در بهینه‌ها محلی می‌افتد. برای حل مسائلی که بین متغیرهایش روابط جفتی  وجود دارد، در نظر گرفتن گرافی با رئوسی (متناظر با متغیر‌های مساله) که بدون هیچ یالی در بین‌شان و کاملاً مستقل از هم هستند چندان مفید به نظر نمی‌رسد. در چنین مواردی بهتر است گراف را کاندید مدل شود که بر اساس اطلاعات بهینه‌سازی بین متغیر‌ها بین آنها روابط دوتایی در نظر بگیرد. همانطور که از درس گسسته بخاطر مانده چنین گرافی قطعاً یک درخت یا مجوعه‌ای از درخت‌هاست. بر طبق این ساختار تا کنون الگوریتم‌هایی مثل الگوریتم بیشینه‌سازی اطلاعات دوطرفه برای خوشه‌بندی ورودی یا  MIMIC، الگوریتم ترکیب بهینه‌سازها با درخت اطلاعات دوطرفه یا COMIT  و الگوریتم توزیع کناری دو متغیره یا BMDA  گرفته شده‌اند. در این فصل به شرح و انواع بسط این الگوریتم‌ها می‌پردازیم.ادامه دارد … ادامه را در فایل pdf انتهای پست ببینید. 

فصل ششم: مدل چند متغیره
6-1 مقدمه
همانطور که در فصل‌های قبل به آن اشاره شد، برای رفع ایرادات وارده بر مدل یک متغیره به سراغ مدل‌های دو متغیره رفتیم. تمام الگوریتم‌هایی که در فصل 5 به آنها پرداخته شد گرچه نسبت به الگوریتم‌هایی که هیچ ارتباطی بین متغیرها در نظر نمی‌گیرند، گستره وسیع‌تری از مسائل را پوشش می‌دهند، رفتار بهتری دارند، اما برای وابستگی‌های از مرتبه بالاتر از 2 بازهم شاهد همان مشکل قبلی هستیم.
بدنباله آنچه تا کنون گفتیم، در این فصل طبعاً قصد داریم در مورد مدل‌هایی با روابطی از مرتبه بالاتر بین متغیرها بحث به میان آوریم. مدل‌هایی که در این فصل بعنوان مدل‌های معروف ارائه می‌شوند شامل الگوریتم توزیع فاکتورگیری شده یا FDA ، الگوریتم ژنتیک متراکم توسعه یافته یا ECGA ، الگوریتم بهینه سازی بیزی یا BOA  و الگوریتم تخمین شبکه‌های بیزی یا EBNA  می‌باشند که همگی از وابستگی‌های مراتب بالا برای متغیرهایشان استفاده می‌کنند.ادامه دارد … ادامه را در فایل pdf انتهای پست ببینید. 

فصل هفتم: پیچیدگی محسباتی
7-1 مقدمه
همانطور که در فصل‌های قبل گفته شد، الگوریتم تخمین توزیع و الگوریتم ژنتیک کلاسیک هر دو از نوع الگوریتم‌های بهینه‌سازی هستند. اما الگوریتم تخمین توزیع دارای توانایی‌های آشکاری در مقابل الگوریتم ژنتیک کلاسیک هستند و البته این موضوع بخاطر ساخت مدلی از شرایط حاکم بر مساله است. در واقع دید این الگوریتم‌ها به مساله تنها منحصر به شایستگی افراد جمعیت نیست. این توانایی باعث شده تا نتایج این الگوریتم همواره در بالایی نمودار‌ها قرار بگیرد و به همین دلیل از سوی بسیاری از محققین کارهای بسیاری روی آنها صورت گرفته است.
اما این تنها چیزی نیست باعث جذابیت این الگوریتم شده‌است. باید به این موضوع اشاره کرد که بر خلاف الگوریتم ژنتیک کلاسیک، الگوریتم تخمین توزیع از پشتوانه قوی ریاضی بهر‌ه می‌برد و این باعث می‌شود که در هنگام کار با این الگوریتم اطمینان بیشتری برای ما وجود داشته باشد.
در این فصل قصد ارائه خلاصه‌ای از تمام اثبات‌های ریاضی موجود در این زمینه را داریم.ادامه دارد … ادامه را در فایل pdf انتهای پست ببینید. 

لیست عبارت های خلاصه شده و معادل کامل آنها
  • Univariate Marginal Distribution Algorithm (UMDA)
  • Population Based Incremental Learning (PBIL)
  • Compact Genetic Algorithm (CGA)
  • Pairwise interaction
  • Mutual Information Maximaization for Input Clustering (MIMIC)
  • Combining Optimizers with Mutual Information Trees (COMIT)
  • Bivariate Marginal Distribution Algorithm (BMDA)
  • Factorized Distribution Algorithm (FDA)
  • Extended Compact Genetic Algorithm (ECGA)
  • Bayesian Optimization Algorithm (BOA)
  • Estimation of Bayesian Networks Algorithm (EBNA)
تشکر و قدردانی:

وبسایت محاسبات تکاملی به نوبه خود، از جناب آقای محمد خجسته فرد در ‫‫ﮔﺮوه ﻫﻮش ﻣﺼﻨﻮﻋﯽ‬ داﻧﺸﮑﺪه ﻣﻬﻨﺪﺳﯽ ﺑﺮق و ﮐﺎﻣﭙﯿﻮﺗﺮ‬ دانشگاه صنعتی اصفهان، به خاطر تهیه و نگارش این اثر ارزشند علمی و به اشتراک گذاشتن آن با سایر دانشجویان علاقه مند در وبسایت محاسبات تکاملی تشکر و قدردانی می نماید.

لینک دانلود فایل کامل در قالب پی دی اف در زمینه الگوریتم های تخمین توزیع
فایل کامل را می توانید از لینک زیر دانلود کنید. جهت دانلود روی لینک زیر کلیک رایت کرده و گزینه “save as یا save link as” را انتخاب نمایید. در صورت نیاز به پسورد در هر مرحله ای دقیقاً عبارت زیر (آدرس وبسایت محاسبات تکاملی) را وارد نمایید.
www.icasite.info
شما نیز اگر اثری در این حوزه خلق کرده اید، با انتشار آن در وبسایت محاسبات تکاملی، دانش خود را با دیگر علاقه مندان این حوزه به اشتراک بگذارید. بخش تماس با ما و همکاری با ما را ببینید.
0 پاسخ

دیدگاه خود را ثبت کنید

تمایل دارید در گفتگوها شرکت کنید؟
در گفتگو ها شرکت کنید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *