۲ -۴- الگوریتم ژنتیک^[۴۵]
الگوریتم ژنتیک روش جستجوی احتمالاتی فراگیر است که از فرایند تکامل زیست شناختی طبیعی پیروی می کند]۱۵[.
این الگوریتم، به نحو موثری در حل مسائل بهینه سازی، به خصوص مسائل غیرخطی و گسترده، کاربرد دارد.
۲-۴-۱- مفهوم الگوریتم ژنتیک
مفهوم الگوریتم ژنتیک از نظریه های چارلز داروین^[۴۶] مبنی بر سیرتکاملی موجودات زنده و تنازع بقاء و ادامه حیات افراد شایسته تر و تولیدمثل آنها و نظریه و آزمایشات گرگور مندل^[۴۷] (بنیانگدار علم توارث ) در تولید ویژگی های مورد انتظار و یا جدیدتر از طریق پیوند گیاهان با ویژگی های مختلف از یک گونه الهام گرفته شده است]۱۵[.
۲- ۴- ۲- آشنائی با الگوریتم ژنتیک
الگوریتم ژنتیک یکی از توانمندترین روش های هوشمند است که با الهام از علم وراثت در حل مسائل غیر خطی و پیچیده ریاضی در کنار روش های هوشمند دیگر از قبیل روش هجوم ذرات^[۴۸]، جستجوی غذای باکتری^[۴۹] E-Coli، شبیه سازی حرارتی^[۵۰]، شبکه های عصبی، کولونی مورچگان^[۵۱] و … کاربرد دارد.
الگوریتم ژنتیک اولین بار توسط دانشمند علوم رایانه دانشگاه میشیگان بنام جان هلند^[۵۲] معرفی گردید]۱۵[.
در موجودات زنده، تولیدمثل از طریق جفت گیری سلول های جنسی صورت می گیرد و هر کدام از سلول ها، حاوی یک یا چند کروموزوم^[۵۳] می باشند. کروموزوم ها حاوی تعداد زیادی ژن^[۵۴] می باشند که این ژن ها نماینده ویژگی های مخصوصی از موجودات مثلا رنگ چشمان است که صورت های مختلف این ویژگی، رنگ چشم آبی، سبز و … است]۱۵[.
از لحاظ مهفومی در این تحقیق فرض شده است که می خواهیم موجودی تک کوروزومی با ویژگی های موردنظر از قبیل وزن، قد، زیبائی، رنگ چشم، رنگ مو و … تولیدکنیم. تعدادی موجود تک کوروموزومی را بصورت تصادفی جهت شروع در نظر می گیریم. کوروموزوم ها را ابتدا برحسب ویژگی های مطلوب مذکور با دادن وزن ها و اهمیت مختلف، ارزیابی می کنیم. چنانچه بهترین کوروموزوم (با بهترین ارزیابی ) شرائط مطلوب را داشته باشد مورد قبول واقع می گیرد، در غیر این صورت به تعداد معینی، کوروموزوم های با بالاترین ارزیابی نسل موجود را درنظر گرفته و برای تولید باقیمانده کوروموزوم های دیگر، از میان کورموزوم های با بالاترین ارزیابی، کورموزوم هائی را به طور تصادفی انتخاب و جهت تبادل ژن ها با یکدیگر ترکیب می کنیم. سپس بطور تصادفی، ژن هائی از کوروموزوم ها را انتخاب و مقدار آنها را (در محدوده قابل قبول ) تغییر می دهیم. بعد، همه کوروموزوم ها را بر حسب نمره ارزیابی شان مرتب می کنیم. مراحل ذکر شده تا برآورده شدن شرائط مطلوب تکرار می کنیم.

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

بعد از این واژه های ساختار و بیت را به جای کلمه های کوروموزوم و ژن، بکار می بریم.
۲-۴-۳- مراحل الگوریتم ژنتیک
الگوریتم ژنتیک جهت رمزگذاری^[۵۵] ساختارها و تولید ساختارهای شروع و انتخاب ساختارها برای تکرارهای بعدی، دارای مراحلی است که بطور اجمالی به شرح ذیل توضیح داده می شود:
۲-۴-۴- ایجاد ساختار اولیه
اولین گام در الگوریتم ژنتیک، تولید ساختارهای اولیه است. ساختار اولیه می بایستی به طور مناسبی کدگذاری گردد. روش های کدگذاری متعددی برحسب نوع مسئله، وجود دارد. مهمترین روش کدگذاری، دوگان^[۵۶] و حقیقی^[۵۷] می باشد.
۲-۴-۵- تولید ساختارهای جدید
ایجاد ساختارهای جدید بدین صورت است که تعدادی از بهترین ساختارها را درنظرگرفته و از بین این ساختارها، تعداد حضور هر ساختار را به طور تصادفی براساس میزان شایستگی آنها طی روش انتخاب موردنظر تعیین و ساختارهای مذکور دو به دو و بطور تصادفی برای تولید باقیمانده ساختارها، انتخاب و با یکدیگر تلاقی می دهیم، که این عمل را تقاطع^[۵۸] می نامیم. سپس بطور تصادفی تعدادی بیت، از کل ساختارها را انتخاب و مقدار آنها را در محدوده قابل قبولی، تغییر می دهیم که این عمل را هم جهش^[۵۹] می نامیم. سپس کل ساختارهای موجود و ایجاد شده دوباره مورد ارزیابی قرارگرفته و برجسب نتیجه ارزیابی مرتب می گردند، اگر بهترین ساختار حائز شرائط مطلوب بود، جواب مسئله است، در غیر این صورت مراحل تولید ساختار جدید تا بدست آمدن ساختار بهینه، ادامه پیدا می کند.
۲- ۴-۶- روش های انتخاب^[۶۰]
دراین مرحله با محاسبه مقدار تابع هدف، به هر ساختار ارزشی تعلق می گیرد که این ارزش میزان گرایش به ساختارهای با ارزش بالاتر را تعیین می کند. به عبارت دیگر تعداد دفعات حضور یک ساختار در تقاطع با ساختارهای دیگر را مشخص می کند. برای انتخاب ساختارها روش های متنوع زیادی وجود دارد که در اینجا فقط به متداول ترین روش ها، پرداخته می شود:
۲-۴-۶-۱- انتخاب چرخ گردان^[۶۱]
در این روش پس از محاسبه مقدار تابع هدف برای هر ساختار، درصد نسبی مقدار تابع هدف هر ساختار از مجموع مقدار تابع هدف کلیه ساختارها را بدست آورده و درصدهای بدست آمده ساختارها را بر روی محیط کامل یک چرخ گردان می گسترانیم. سپس این چرخ گردان را مقابل یک فلش می چرخانیم. تعداد دفعاتی که فلش مذکور بر روی قطاع متناسب با هر ساختار قرار می گیرد، نشان دهنده تعداد انتخاب هر ساختار برای تقاطع با ساختارهای دیگر است.
در یک روش دیگر از روش های چرخ گردان، بجای یک فلش از تعدادی فلش برابر تعداد کل ساختارها استفاده و چرخ گردان را فقط یک بار می چرخانیم.
۲-۴-۶-۲- انتخاب مسابقه ای^[۶۲]
این شیوه انتخاب به جای استفاده از مقدار و یا درصد نسبی تابع هدف ساختارها، از رتبه هر ساختار استفاده می کند. روش کار به این صورت است که هر بار K ساختار به طور تصادفی و با احتمال برابر از میان ساختارها انتخاب می شوند. سپس از میان K ساختار تعدادی را که بالاترین رتبه را دارند انتخاب و بقیه حذف می گردند، این عمل را به تعداد کل ساختارها تکرار می کنیم]۱۵[.
۲-۴-۶-۳- انتخاب رتبه ای^[۶۳]
در این روش از مقدار یا درصد نسبی تابع هدف برای انتخاب استفاده نمی شود، بلکه از رتبه هر ساختار نسبت به یکدیگر استفاده می گردد.
۲-۴-۷- تقاطع
روش های تقاطع متعددی با توجه به نوع کدگذاری ساختارها وجود دارد که به طور مختصر به دو روش کلی به صورت ذیل اشاره می گردد:
۲-۴-۷-۱- تقاطع تک نقطه ای^[۶۴]
در این روش، ساختارهای انتخاب شده، از یک نقطه (که به طور تصادفی انتخاب می شود ) دو به دو با یکدیگر تلاقی یافته و از آن نقطه هر ساختار به دو قسمت تقسیم و یک قسمت از هرکدام با یکدیگر مبادله می شود.
۲-۴-۷-۲- تقاطع چند نقطه ای^[۶۵]
در این روش، به طور تصادفی در چندین نقطه ساختارها با یکدیگر تلاقی یافته و چندین قسمت بین دو ساختار انتخاب و مبادله می گردد.
۲-۴-۸- جهش
در این جا هم روش های جهش^[۶۶] متعددی با توجه به نوع کدگذاری ساختارها وجود دارد که به طور مختصر به دو روش کلی به صورت ذیل اشاره می گردد:
۲-۴-۸-۱- جهش تک نقطه ای^[۶۷]
در این روش با احتمال بسیار کم تعیین شده، به طور تصادفی در یک بیت از ساختار انتخاب شده از میان کل ساختارها، در محدوده قابل قبولی، تغییر ایجاد می کنیم.
۲-۴-۸-۲- جهش چند نقطه ای^[۶۸]
در این روش نیز با احتمال بسیار کم تعیین شده، به طور تصادفی در چند بیت از ساختار انتخاب شده از میان کل ساختارها، در محدوده قابل قبول، تغییر ایجاد می کنیم.
۲- ۴- ۹- پردازش و برازش^[۶۹]
گرچه در حل مسائل با الگوریتم ژنتیک نیازی به دانستن دقیق ساختار ریاضی مسائل نیست، ولی باید بتوانیم به صریقی میزان مطلوبیت هر ساختار بالقوه را ارزیابی کنیم. آنگاه با حفظ ساختارهای مناسب تر و حذف ساختارهای کمتر مناسب، به ساختار مناسب نزدیک شویم. میزان مطلوبیت ساختارها توسط تابع هدف یا تابع برازش تعیین می گردد. در الگوریتم ژنتیک و سایر روش های کلاسیک (برنامه ریزی خطی، برنامه ریزی اعداد صحیح، لاگرانژو … )، هدف کمینه و بیشینه سازی تابع هدف مسئله می باشد.
۲-۴-۱۰- جایگزینی^[۷۰]
مرحله جایگزینی در واقع مکمل مراحل انتخاب، تقاطع و جهش است. در این مرحله ساختارهائی که باید با ساختارهای جدید تعویض شوند، مشخص می شوند. در الگوریتم ژنتیک استاندارد از روش جایگزینی تکرار به تکرار استفاده می شود. در این شیوه جایگزینی، تمام ساختارهای موجود با ساختارهای جدید جایگزین می شود. در الگوریتم ژنتیک حالت پایدار، ساختار ایجاد شده، تنها در صورتی جایگزین ساختارهای به وجود آورنده خود می شود که میزان شایستگی بهتری داشته باشد. بنابراین تنها بخشی از ساختارهای جاری در هر تکرار تعویض می شوند و ساختاری، می تواند در تکرارهای متعدد پایدار بماند. در الگوریتم ژنتیک تدریجی، ساختار جدید یا با یکی از ساختارهای به وجود آورنده خود و یا با به طور تصادفی جانشین ساختار دیگری شده و یا به جای ساختار با کمترین میزان شایستگی قرار گرفته و یا جایگزین شبیه ترین ساختار به خود می شود. در الگوریتم ژنتیک با رویکرد حفظ خبرگان، تعدادی از ساختارها با بالاترین میزان شایستگی از یک تکرار به تکرار دیگر عینا انتقال می یابند. چنانچه در عمل تقاطع شرکت داده شوند ساختارهائی را که به وجود می آورند جایگزین این ساختارها نمی گردند]۱۵[.
۲-۵- معرفی دو تابع کاربردی sparse و graphtraverse در نرم افزار matlab
در این بخش به معرفی دو تابع مهم و کاربردی sparse و graphtraverse در نرم افزار matlab پرداخته می شود:
۲-۵-۱- ماتریس sparse
ماتریس sparse برای تحلیل عددی ماتریس های بزرگ با اکثریت اعضای صفر، کاربرد دارد که توسط هاری مارکویتز^[۷۱] اختراع گردید.
در لغت sparse matrixبه معنی ماتریس کم پشته می باشد، ماتریسی است که اکثریت اعضای آن صفر می باشد، همچنین به ماتریسی که اکثریت اعضای آن غیر صفر باشد، ماتریس متراکم^[۷۲] گویند.
ماتریس کم پشته در حوزه های تئوری شبکه با اتصالات و یا اطلاعات کم ولی مهم، مفهوم و کاربرد زیادی دارد. اغلب در رشته های مهندسی و علوم، جهت حل معادلات تفاضلی جزئی، با ماتریس های کم پشته زیادی سروکار داریم.
با توجه به اینکه استفاده از ماتریس های کم پشته، بدلیل کاستن از حجم محاسبات، به زمان کمتری نیاز داشته و حافظه کمتری از رایانه را نیز اشغال می کند، مورد توجه و استفاده قرار می گیرد..
در حالت عادی، یک ماتریس کم پشته، یک بردار دو بعدی است. هر عضو بردار بیانگر یک عنصرaij از ماتریس است که از طریق دو اندیس i و j قابل دسترسی است. i تعداد سطر و j تعداد ستون ماتریس را نشان می دهد. برای یک ماتریس m×n حافظه کافی برای ذخیره اطلاعات به تعداد m×n مکان می باشد. این مقدار حافظه ازطریق ذخیره فقط عنصرهای غیرصفر کاهش می یابد.