بایگانی برچسب برای: پلاک خوان

ترکیب و تشخیص صحبت

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

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

ترکیب و تشخیص کامپیوتری صحبت مسائل دشواری هستند. روشهای مختلفی مورد آزمایش قرار گرفت هاند که موفقیت کمی داشته‌اند. این زمینه از زمینه‌های فعال در تحقیقات پردازش سیگنال دیجیتال (دی. اس. پی) بوده و بدون شک سالها این گونه خواهد ماند. در حال حاضر از ابزارهای برنامه‌نویسی جاافتاده در زمینه‌های برشمرده شده می‌توان به‌ای. پی. آی صحبت شرکت مایکروسافت اشاره نمود که دارای تواناییهای عمدهای در زمینه‌های تشخیص و ترکیب صحبت است و توانایی آن تا حدی گسترده‌است که در محصول بزرگ واز آن استفادهٔ عملی شده‌است. ابزار عمد هی دیگر تولید شرکت آی. بی. ام است و MS افیس xpتوانمند نام دارد که به لحاظ پشتیبانی آن برای سیستم‌عاملهای متعدد و زبانهای گوناگون از اهمیت خاصی برخوردار است.

مدلی برای توصیف روش تولید صحبت

تقریباً تمام تکنیکهای ترکیب و تشخیص صحبت بر اساس مدل تولید صحبت انسان که در شکل شماره ۳ نشان داده شده‌است ایجاد شده‌اند. بیشتر صداهای مربوط به صحبت انسان به دو دستهٔ صدادار و سایشی تقسیم می‌شوند. اصوات صدادار وقتی که هوا از ریه‌ها و از مسیر تارهای صوتی به بیرون دهان یا بینی رانده می‌شوند ایجاد می‌گردند. تارهای صوتی دو رشتهٔ آویخته از بافت هستند که در مسیر جریان هوا کشیده شده‌اند. در پاسخ به کشش ماهیچه‌های متفاوت تارهای صوتی با فرکانسی بین ۵۰ تا ۱۰۰۰ هرتز ارتعاش می‌کنند که باعث انتقال حرکتهای متناوب هوا. در مقایسه، اصوات سایشی به صورت نویز تصادفی و نه حاصل از ارتعاش تارهای صوتی به وجود می‌آیند. این حادثه زمانی رخ می‌دهد که تقریباً جریان هوا به وسیلۀ زبان و لبها یا دندانها حبس می‌شود که این امر باعث ایجاد اغتشاش هوا در نزدیکی محل فشردگی می‌گردد شکل شماره ۳ – مدل صحبت انسان. در یک تکه زمان کوتاه، حدود ۲ تا ۴۰ میلی ثانیه صحبت می‌تواند با استفاده از سه پارامتر مدلسازی شود:

۱- انتخاب یک آشفتگی متناوب یا نویزوار. ۲- پیچ آشفتگی متناوب ۳- ضرایب یک فیلتر خطی بازگشتی که پاسخ اثر صوتی را تقلید می‌کند. اصوات سایشی زبان انگلیسی عبارتند از S،Z،TH استفاده از یک مولد نویز نشان داده شده‌اند. هر دو نوع این اصوات، توسط چاله‌های صوتی که از زبان، لبها، دهان، گلو و گذرگاه‌های بینی تشکیل شده‌اند دچار تغییر می‌شوند. چون انتشار صدا در این ساختارها یک فرایند خطی است می‌تواند با استفاده از یک فیلتر خطی با یک پاسخ ضربهٔ مناسب نمایش داده شود. در بیشتر موارد از یک فیلتر بازگشتی که ضرایب بازگشتی آن ویژگیهای فیلتر را مشخص می‌کند استفاده می‌شود. به خاطر این که چاله‌های صوتی ابعادی به اندازهٔ چند سانتیمتر دارند پاسخ فرکانسی یک دنباله از تشدیدها با اندازه‌های کیلوهرتزی است. در اصطلاح پردازش صوت این قله‌های تشدید فرکانسهای فرمانت خوانده می‌شوند. با تغییر جایگاه نسبی زبان و لبها فرکانسهای فرمانت هم از لحاظ دامنه و هم از لحاظ فرکانس ممکن است تغییر کنند.

سیگنال صوتی به تکه‌های کوچک به اندازهٔ ۲ تا ۴۰ میلی ثانیه تقسیم می‌شوند و از الگوریتم اف. اف. تی برای یافتن طیف فرکانسی هر تکه استفاده می‌شود. این طیفها در کنار هم قرار داده شده تبدیل به یک تصویر سیاه و سفید می‌شود (دامنه‌های پایین روشن و دامنه‌های بالا تیره می‌شوند). این کار یک روش گرافیکی برای مشاهدهٔ این که چگونه محتویات فرکانسی صحبت با زمان تغییر می‌کند به وجود می‌آورد. اندازهٔ هر تکه بر اساس اعمال یک بده بستان بین دقت فرکانسی (که با تکه‌های بزرگ تر بهتر می‌شود) و دقت زمانی (که با تکه‌های کوچک تر بهتر می‌شود) انتخاب می‌گردد.

ویژگیهای عمومی اصوات d و c ویژگیهای عمومی اصوات صدادار و شکلهای b و a دارای موج صوتی متناوبی مانند آنچه در رین در a همچنانکه در شکل ۴ دیده می‌شود اصوات صدا دار مثل نشان داده شده و طیف فرکانسی آنها که عبارت است از یک دنباله از همسازهای با اندازهٔ منظم a شکل دارای یک سیگنال نویزی در دامنهٔ استوم در s می‌باشد در مقابل، اصوات سایشی مانند b مانند شکل هستند. این طیفها همچنین شکل فرکانسهای فرمانت برای d و یک طیف نویزی مانند شکل c زمان مانند شکل در هر رین هر دو نوع صوت نشان می‌دهند. همچنین به این نکته توجه کنید که نمایش زمان-فرکانس کلمهٔ دو باری که ادا شده شبیه به هم است. در یک دور هی کوتاه برای نمونه ۲۵ میلی ثانیه یک سیگنال صحبت می‌تواند با مشخص کردن سه پارامتر تقریب زده شود:

۱) انتخاب یک اغتشاش متناوب یا نویزوار

۲)فرکانس موج متناوب (اگر مورد استفاده قرار گرفته باشد)

۳)ضرایب فیلتر دیجیتالی که برای تقلید پاسخ تارهای صوتی استفاده شده‌است.

صحبت پیوسته با به‌روزآوری این سه پارامتر به صورت پیوسته به انداز هی ۴۰ بار در ثانیه ترکیب شود. این نامیده می‌شود و یک وسیلهٔ «صحبت و املا» راهکار برای یکی از کاربردهای تجاری دی. اس. پی که الکترونیکی پرفروش برای بچه هاست مناسب است. کیفیت صدای این نوع ترکیب کنندهٔ صحبت پایین است و بسیار مکانیکی و متفاوت با صدای انسان به نظر می‌رسد. ولی در هر صورت نرخ دادهٔ خیلی پایینی در حدود چند کیلوبیت بر ثانیه نیاز دارد.

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

الگوریتمهای تشخیص صحبت با تلاش برای شناسایی الگوهای پارامترهای استخراج شده از این روش نیز پیش تر می‌روند. این روشها معمولاً شامل مقایس هی تکه‌های اطلاعاتی با قالبهای صدای از پیش ذخیره شده در تلاش برای تشخیص کلمات گفته شده می‌باشند. مشکلی که در اینجا وجود دارد این است که این روش همیشه به درستی کار نم یکند. این روش برای بعضی کاربردها قابل استفاده‌است اما با تواناییهای شنوندگان انسانی خیلی فاصله دارد.

آیندهٔ فناوریهای پردازش صحبت

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

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

هدفی که این نرم‌افزار دنبال می‌کند آن است که به جای برقراری ارتباط با کامپیوتر توسط ماوس و صفحه کلید و… خود بتوان پیام موردنظر را بیان کرده و کامپیوتر آن فرمان مربوطه را انجام دهد یا به جای تایپ کردن متن موردنظر فقط کافی است که متن موردنظر را از طریق میکروفون به رایانه منتقل کرده و متن را تایپ شده و آماده ببنیم. هدفی که این نرم‌افزار همانند بسیاری از نرم‌افزارهای دیگر دنبال می‌کند ارتقای سطح کیفیت زندگی و تسهیل امور روزمره‌است در صورت استفاده از این نرم‌افزار در ادارات و سازمان‌های دولتی است.

منبع


مقدمه ای بر پردازش گفتار

سیگنال صوتی و شنیداری یا Audio احساس ارتعاشات و نوسانات هوا توسط گوش انسان است. اگر این صوت در محدوده فرکانسی 20Hz – 20KHz  باشد با رسیدن به گوش و سپس انتقال به مغز و پردازش روی آن باعث درک مفهوم در ذهن انسان می گردد. سیگنال گفتار Speech زیر مجموعه ای از سیگنال Audio می باشد که توسط انسان ایجاد می شود. در نمودار زیر بخش سیاه شنیده نمی شود, شنیدن بخش قرمز آزار دهنده است و بخش سبز شنیده می شود.

نمودار بازه شنوایی

از جمله کاربردهای پردازش گفتار میتوان به موارد زیر اشاره کرد:

  • مخابره صدا به همراه تصوير و سایراطلاعات
  • دادن فرمانها و دستورات كنترلي توسط صدا
  • كنترل دستگاه ها و تجهيزات صنعتي و آزمايشگاهها توسط صدا
  • دادن فرامين صوتي در جاهايي كه دست انسان مشغول است مثل هواپيما و اتوموبيل
  • ديكته اتوماتيك
  • انجام عملیات بانکی پس از تایید هویت توسط صدا
  • کلید و قفل صوتی و بازشناسی هویت افراد قبل از ورود آنها به اماکن با درجه امنیت بالا
  • شناسائی خودکار زبان گوینده در سیستم های ترجمه اتوماتیک و یا پذیرش هتل های بین المللی
  • فروش خودکار بلیط در ایستگا ه های قطار و مترو و اتوبوس و غیره
  • پردازش زبان برای نا بینایان

اکثر کاربردهای ذکر شده در یکی از سه شاخه زیر قرار میگیرند:

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

اما بطور کلی میتوان موارد زیر را به عنوان شاخه های پردازش گفتار نام برد:

  • کد کردن و فشرده سازی گفتار
  • سنتز گفتار
  • تشخیص و درک گفتار
  • تأیید هویت گوینده
  • تشخیص هویت گوینده
  • غنی سازی گفتار
  • ترجمه شفاهی گفتار
  • تعیین سن، جنس، لهجه، حالت روحی و روانی و نا هنجاری گفتار

برای تولید گفتار بسیاری از اندام ها به صورت هماهنگ نیاز به فعالیت دارند. که بطور کلی میتوان آن ها را در دو بخش vocal tract  و  nasal tract تقسیم بندی کرد.

Vocal Tract: شامل حلق(اتصال از مری به دهان) و محفظه دهانی میباشد. میانگین طول vocal tract برای آقایان حدود 17.5 سانتیمتر میباشد و سطح مقطع آن که توسط موقعیت زبان, لبها, فک و غشا(یک دریچه در پشت محفظه دهانی که vocal tract و nasal tract را برای تولید صداهای دماغی شبیه /m/,/n/ به هم وصل می کند) تعیین میگردد و از صفر(بسته شدن کامل) تا 20 سانتیمتر مربع متفاوت است.

Nasal Tract: از غشا تا سوراخ بینی گفته میشود.

 

اندام های داخلی دخیل در گفتار انسان

 

با کمک اندام های گفتاری میتوانیم صداهای متفاوتی ایجاد کنیم و با کنار هم قرار گرفتن پیوسته این صداها گفتار شکل میگیرد به عنوان مثال شکل مجرای گفتار را در هنگام ادای بعضی حروف به شکل زیر داریم:

شکل مجرای گفتار در هنگام ادای بعضی حروف

واکه ها (vowel) و همخوانهای(consonant) زبان فارسی با توجه به شیوه تولید و واک(voice) یا بی واک(unvoice) بودن در جدول زیر قابل مشاهده هستند:

جدول واکه ها و همخوان های زبان فارسی

انواع نویز صوتی در پردازش گفتار

برقراري ارتباط گفتاري در محيط‌هاي آرام و فواصل نزديک معمولا به درستي و بدون دخالت نويز انجام مي‌گيرد، ولي زماني که بحث برقراري ارتباط در فواصل دور مطرح باشد، نويز زمينه در آن فضا وجود دارد و کيفيت سيگنال گفتار تا حد زيادي کاهش مي‌يابد؛ در نتيجه توانايي شنونده تضعيف مي‌گردد. نکته حائز اهميت در ارائه يک روش حذف نويز، حفظ ساختار اصلي سيگنال مي‌باشد؛ بطوريکه سيگنال بهبود يافته، نسبت به سيگنال اصلي دچار تغيير شکل، جابجايي و اعوجاج نشود.

 

بر اساس ماهيت و ويژگي‌هاي منبع نويز، نويز مي‌تواند به صورت زیر دسته‌بندي شود:

    • نويز زمينه: منظور از نويز زمينه صداهايي است بـه جـز صداي فـرد گوينده کـه توسط ميکروفون دريافت شده است و معمولاً به دو دسته نويز سفيد و نـويز رنگـي تقـسيم مـي شود. مانند صداي به هم خوردن يک در، موزيک، همهمه افراد و غيره. نويز جمع شونده اسـت، کـه معمولاً با سيگنال ناهمبسته است و در محيط هاي مختلفي مثل ماشين، دفتر کار، خيابان‌هاي شهر، محيط کارخانه، هليکوپتر و غيره حاضر است. نويزهاي خيابان و کارخانه و … ويژگي‌هاي پوياي بسياري دارند. نويز کارخانـه وهليکـوپتر اجـزاء پريوديکي دارند و مثال‌هايي از نويز غير ايستا هستند که ويژگي‌هاي متغير در زماني دارند.
    • گوينده مزاحم(گفتاري که مانند نويز است): نويز جمع شونده‌ای که ترکيبي از يـک يـا چنـد گوينده است. در اين نوع، خصوصيات نويز و بازه فرکانسي‌اش بسيار مـشابه بـا سيگنال گفتـار مورد نظر است.
    • نويز ضربه‌ای: مانند بهم خوردن شدید درب، یا نويز ارشيو شده در صفحات گرامافون.
    • نويز غير افزايشي به دليل تاکيد گوينده: براي مثال اثر لمبارد، اثر نويز وقتي که گوينده تمايل به افزايش صدايش را دارد.
    • نويز همبسته با سيگنال: مانند طنين و اکوها
    • نويز کانولوشني: مشابه با کانولوشن در حوزه زمان. براي نمونه، تغييرات در سيگنال گفتـار به علت تغييرات در خواص صوتي اتاق يا تغييرات در ميکروفون ها و غيره. برخورد با ايـن مـوارد معمولاً دشوارتر از نويزهای جمع شونده است.

منبع


منابع

1.fa.wikipedia.org

2.http://yarcode.ir

پردازش گفتار (صوت) قسمت 1
پردازش گفتار (صوت) قسمت 2

بهينه‌سازی يك فعاليت مهم و تعيين‌كننده در طراحي ساختاري است. طراحان زماني قادر خواهند بود طرح‌هاي بهتري توليد كنند كه بتوانند با روش‌هاي بهينه‌سازی در صرف زمان و هزينه طراحي صرفه‌جويي نمايند. بسياري از مسائل بهينه‌سازی در مهندسي، طبيعتاً پيچيده‌تر و مشكل‌تر از آن هستند كه با روش‌هاي مرسوم بهينه‌سازی نظير روش برنامه‌ريزي رياضي و نظاير آن قابل حل باشند. بهينه‌سازی تركيبي (Combinational Optimization)، جستجو براي يافتن نقطه بهينه توابع با متغيرهاي گسسته  (Discrete Variables) مي‌باشد. امروزه بسياري از مسائل بهينه‌سازی تركيبي كه اغلب از جمله مسائل با درجه غير چندجمله‌اي (NP-Hard) هستند، به صورت تقريبي با كامپيوترهاي موجود قابل حل مي‌باشند. از جمله راه‌حل‌هاي موجود در برخورد با اين گونه مسائل، استفاده از الگوريتم‌هاي تقريبي يا ابتكاري است. اين الگوريتم‌ها تضميني نمي‌دهند كه جواب به دست آمده بهينه باشد و تنها با صرف زمان بسيار مي‌توان جواب نسبتاً دقيقي به دست آورد و در حقيقت بسته به زمان صرف شده، دقت جواب تغيير مي‌كند.

 1-مقدمه

هدف از بهينه‌سازي يافتن بهترين جواب قابل قبول، با توجه به محدوديت‌ها و نيازهاي مسأله است. براي يك مسأله، ممكن است جواب‌هاي مختلفي موجود باشد كه براي مقايسه آنها و انتخاب جواب بهينه، تابعي به نام تابع هدف تعريف مي‌شود. انتخاب اين تابع به طبيعت مسأله وابسته است. به عنوان مثال، زمان سفر يا هزينه از جمله اهداف رايج بهينه‌سازي شبكه‌هاي حمل و نقل مي‌باشد. به هر حال، انتخاب تابع هدف مناسب يكي از مهمترين گام‌هاي بهينه‌سازي است. گاهي در بهينه‌سازي چند هدف  به طور همزمان مد نظر قرار مي‌گيرد؛ اين گونه مسائل بهينه‌سازي را كه دربرگيرنده چند تابع هدف هستند، مسائل چند هدفي مي‌نامند. ساده‌ترين راه در برخورد با اين گونه مسائل، تشكيل يك تابع هدف جديد به صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص مي‌شود. هر مسأله بهينه‌سازي داراي تعدادي متغير مستقل است كه آنها را متغيرهاي طراحي می‌نامند كه با بردار n  بعدي x  نشان داده مي‌شوند.

هدف از بهينه‌سازي تعيين متغيرهاي طراحي است، به گونه‌اي كه تابع هدف كمينه يا بيشينه شود.

1-1-مسائل مختلف بهينه‌سازي به دو دسته زير تقسيم مي‌شود:

الف) مسائل بهينه‌سازي بي‌محدوديت: در اين مسائل هدف، بيشينه يا كمينه كردن تابع هدف بدون هر گونه محدوديتي بر روي متغيرهاي طراحي مي‌باشد.

ب) مسائل بهينه‌سازي با محدوديت: بهينه‌سازي در اغلب مسائل كاربردي، با توجه به محدوديت‌هايي صورت مي‌گيرد؛ محدوديت‌هايي كه در زمينه رفتار و عملكرد يك سيستم مي‌باشد و محدوديت‌هاي رفتاري و محدوديت‌هايي كه در فيزيك و هندسه مسأله وجود دارد، محدوديت‌هاي هندسي يا جانبي ناميده مي‌شوند.

معادلات معرف محدوديت‌ها ممكن است  به صورت مساوي يا نامساوي باشند كه در هر مورد، روش بهينه‌سازي متفاوت مي‌باشد. به هر حال محدوديت‌ها، ناحيه قابل قبول در طراحي را معين مي‌كنند.

به طور كلي مسائل بهينه‌سازي با محدوديت را مي‌توان به صورت زير نشان داد:

مسائل بهینه سازی با محدودیت

2-بررسي روش‌هاي جستجو و بهينه‌سازي

پيشرفت كامپيوتر در طي پنجاه سال گذشته باعث توسعه روش‌هاي بهينه‌سازي شده، به طوري كه دستورهاي متعددي در طي اين دوره تدوين شده است. در اين بخش، مروري بر روش‌هاي مختلف بهينه‌سازي ارائه مي‌شود.

شكل 1-1 روش‌هاي بهينه‌سازي را در چهار دسته وسيع دسته‌بندي مي‌كند. در ادامه بحث، هر دسته از اين روش‌ها مورد بررسي قرار مي‌گيرند.

روش های بهینه سازی

1-2- روش‌هاي شمارشي

در روش‌هاي شمارشي (Enumerative Method)، در هر تكرار فقط يك نقطه متعلق به فضاي دامنه تابع هدف بررسي مي‌شود. اين روش‌ها براي پياده‌سازي، ساده‌تر از روش‌هاي ديگر مي‌باشند؛ اما به محاسبات قابل توجهي نياز دارند. در اين روش‌ها سازوکاری براي كاستن دامنه جستجو وجود ندارد و دامنه فضاي جستجو شده با اين روش خيلي بزرگ است. برنامه‌ريزي پويا (Dynamic Programming) مثال خوبي از روش‌هاي شمارشي مي‌باشد. اين روش كاملاً غيرهوشمند است و به همين دليل امروزه بندرت به تنهايي مورد استفاده قرار مي‌گيرد.

2-2- روش‌هاي محاسباتي (جستجوي رياضي يا- Based Method Calculus)

اين روش‌ها از مجموعه شرايط لازم و كافي كه در جواب مسأله بهينه‌سازي صدق  مي‌كند، استفاده مي‌كنند. وجود يا عدم وجود محدوديت‌هاي بهينه‌سازي در اين روش‌ها نقش اساسي دارد. به همين علت، اين روش‌ها به دو دسته روش‌هاي با محدوديت و بي‌محدوديت تقسيم مي‌شوند.

روش‌هاي بهينه‌سازي بي‌محدوديت با توجه به تعداد متغيرها شامل بهينه‌سازي توابع يك متغيره و چند متغيره مي‌باشند.

روش‌هاي بهينه‌سازي توابع يك متغيره، به سه دسته روش‌هاي مرتبه صفر، مرتبه اول و مرتبه دوم تقسيم مي‌شوند. روش‌هاي مرتبه صفر فقط به محاسبه تابع هدف در نقاط مختلف نياز دارد؛ اما روش‌هاي مرتبه اول از تابع هدف و مشتق آن و روش‌هاي مرتبه دوم از تابع هدف و مشتق اول و دوم آن استفاده مي‌كنند. در بهينه‌سازي توابع چند متغيره كه كاربرد بسيار زيادي در مسائل مهندسي دارد، كمينه‌سازي يا بيشينه‌سازي يك كميت با مقدار زيادي متغير طراحي صورت مي‌گيرد.

يك تقسيم‌بندي، روش‌هاي بهينه‌سازي با محدوديت را به سه دسته برنامه‌ريزي خطي، روش‌هاي مستقيم و غيرمستقيم تقسيم مي‌كند. مسائل با محدوديت كه توابع هدف و محدوديت‌هاي آنها خطي باشند، جزو مسائل برنامه‌ريزي خطي قرار مي‌گيرند. برنامه‌ريزي خطي شاخه‌اي از برنامه‌ريزي رياضي است و كاربردهاي فيزيكي، صنعتي و تجاري بسياري دارد.

در روش‌هاي مستقيم، نقطه بهينه به طور مستقيم جستجو شده و از روش‌هاي بهينه‌يابي بي‌محدوديت استفاده نمي‌شود. هدف اصلي روش‌هاي غيرمستقيم استفاده از الگوريتم‌هاي بهينه‌سازي بي‌محدوديت براي حل عمومي مسائل بهينه‌سازي با محدوديت مي‌باشد.

در اكثر روش‌هاي محاسباتي بهينه‌يابي، از گراديان تابع هدف براي هدايت جستجو استفاده مي‌شود. اگر مثلاً به علت ناپيوستگي تابع هدف، مشتق آن قابل محاسبه نباشد، اين روش‌ها اغلب با مشكل روبه‌رو مي‌شوند.

3-2-روش‌هاي ابتكاري و فرا ابتکاری (جستجوي تصادفي)

يك روش ناشيانه براي حل مسائل بهينه‌سازي تركيبي اين است كه تمامي جواب‌هاي امكان‌پذير در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهايت، بهترين جواب انتخاب گردد. روشن است كه شيوه شمارش كامل، نهايتاً به جواب دقيق مسأله منتهي مي‌شود؛ اما در عمل به دليل زياد بودن تعداد جواب‌هاي امكان‌پذير، استفاده از آن غيرممكن است. با توجه به مشكلات مربوط به روش شمارش كامل، همواره بر ايجاد روش‌هاي مؤثرتر و كاراتر تأكيد شده است. در اين زمينه، الگوريتم‌هاي مختلفي به وجود آمده است كه مشهورترين نمونه آنها، روش سيمپلكس براي حل برنامه‌هاي خطي و روش شاخه و كرانه براي حل برنامه‌هاي خطي با متغيرهاي صحيح است. براي مسائلی با ابعاد بزرگ، روش سيمپلكس از كارايي بسيار خوبي برخوردار است، ولي روش شاخه و كرانه كارايي خود را از دست مي‌دهد و عملكرد بهتری از شمارش كامل نخواهد داشت. به دلايل فوق، اخيراً تمركز بيشتري بر روش‌هاي ابتكاري (Heuristic) يا فرا ابتکاری (Metaheuristic) يا جستجوی تصادفی (Random Method) صورت گرفته است. روش‌هاي جستجوي ابتكاري، روش‌هايي هستند كه مي‌توانند جوابي خوب (نزديك به بهينه) در زماني محدود براي يك مسأله ارائه كنند. روش‌هاي جستجوي ابتكاري عمدتاً بر مبناي روش‌هاي شمارشي مي‌باشند، با اين تفاوت كه از اطلاعات اضافي براي هدايت جستجو استفاده مي‌كنند. اين روش‌ها از نظر حوزه كاربرد، كاملاً عمومي هستند و مي‌توانند مسائل خيلي پيچيده را حل كنند. عمده اين روش‌ها، تصادفي بوده و از طبيعت الهام گرفته شده‌اند.

3-مسائل بهينه‌سازي تركيبي (Optimization Problems Combinational)

در طول دو دهه گذشته، كاربرد بهينه‌سازي در زمينه‌هاي مختلفي چون مهندسي صنايع، برق، كامپيوتر، ارتباطات و حمل و نقل گسترش يافته است.

بهينه‌سازي خطي و غيرخطي (جستجو جهت يافتن مقدار بهينه تابعي از متغيرهاي پيوسته)، در دهه پنجاه و شصت از اصلي‌ترين جنبه‌هاي توجه به بهينه‌سازي بود.

بهينه‌سازي تركيبي عبارت است از جستجو براي يافتن نقطه توابع با متغيرهاي گسسته و در دهه 70 نتايج مهمي در اين زمينه به دست آمد. امروزه بسياري از مسائل بهينه‌سازي تركيبي (مانند مسأله فروشنده دوره‌گرد) كه اغلب از جمله مسائل NP-hard  هستند، به صورت تقريبي (نه به طور دقيق) در كامپيوترهاي موجود قابل حل مي‌باشند.

مسأله بهينه‌سازي تركيبي را مي‌توان به صورت زوج مرتب R,C نمايش داد كه R مجموعه متناهي از جواب‌هاي ممكن (فضاي حل) و C  تابع هدفي است كه به ازاي هر جواب مقدار خاصي دارد. مسأله به صورت زير در نظر گرفته مي‌شود:

يافتن جواب به گونه‌اي كه  C  كمترين مقدار را داشته باشد.

مسئله بهینه سازی ترکیبی

1-3-روش حل مسائل بهينه‌سازي تركيبي

روشن است كه شيوه شمارش كامل، نهايتاً به جواب دقيق مسأله منجر مي‌شود؛ اما در عمل به دليل زياد بودن تعداد جواب‌هاي امكان‌پذير، استفاده از آن بي‌نتيجه است. براي آنكه مطلب روشن شود، مسأله مشهور فروشنده دوره‌گرد (TSP) را در نظر مي‌گيريم.

اين مسأله يكي از مشهورترين مسائل در حيطه بهينه‌سازي تركيبي است که بدين شرح می‌باشد:

تعيين مسير حركت يك فروشنده بين N شهر به گونه‌اي كه از هر شهر تنها يكبار بگذرد و طول كل مسير به حداقل برسد، بسيار مطلوب است. تعداد كل جواب‌ها برابر است با  !   . فرض كنيد كامپيوتري موجود است كه مي‌تواند تمام جواب‌هاي مسأله با بيست شهر را در يك ساعت بررسي كند. بر اساس آنچه آورده شد، براي حل مسأله با 21 شهر، 20 ساعت زمان لازم است و به همين ترتيب، زمان لازم براي مسأله 22 شهر، 5/17 روز و براي مسأله 25 شهر، 6 قرن ا ست!

به دليل همين رشد نمايي زمان محاسبه، شمارش كامل روشي كاملاً نامناسب است.

همان طور که گفته شد، با توجه به مشكلات مربوط به روش شمارش كامل، همواره بر ايجاد روش‌هاي مؤثرتر و كاراتر تأكيد شده است. در اين زمينه، الگوريتم‌هاي مختلفي به وجود آمده كه مشهورترين آنها، الگوريتم سيمپلكس براي حل برنامه‌هاي خطي و روش شاخه و كران براي حل برنامه‌هاي خطي با اعداد صحيح است.

بنابراين در سال‌هاي اخير توجه بيشتري بر روش‌هاي ابتكاري برگرفته از طبيعت كه شباهت‌هايي با سيستم‌هاي اجتماعي يا طبيعي دارد، صورت گرفته است و نتايج بسيار خوبي در حل مسائل بهينه‌سازي تركيبي NP-hard به دنبال داشته است. در اين الگوريتم‌ها هيچ ضمانتي براي آنكه جواب به دست آمده بهينه باشد، وجود ندارد و تنها با صرف زمان بسيار مي‌توان جواب نسبتاً دقيقي به دست آورد؛ در حقيقت با توجه به زمان صرف شده، دقت جواب تغيير مي‌كند.

براي روش‌هاي ابتكاري نمي‌توان تعريفي جامع ارائه كرد. با وجود اين، در اينجا كوشش مي‌شود تعريفي تا حد امكان مناسب براي آن عنوان شود:

روش جستجوي ابتكاري، روشي است كه مي‌تواند جوابي خوب (نزديك به بهينه) در زماني محدود براي يك مسأله ارائه كند. هيچ تضميني براي بهينه بودن جواب وجود ندارد و متأسفانه نمي‌توان ميزان نزديكي جواب به دست آمده به جواب بهينه را تعيين كرد.

در اينجا مفاهيم برخي از روش‌هاي اصلي ابتكاري بدون وارد شدن به جزييات معرفي مي‌شود.

1-1-3- آزاد‌سازي

آزادسازي (Relaxation)، يكي از روش‌هاي ابتكاري در بهينه‌سازي است كه ريشه در روش‌هاي قطعي بهينه‌سازي دارد. در اين روش، ابتدا مسأله به شكل يك مسأله برنامه‌ريزي خطي عدد صحيح         LIP) = Linear Litegar Programmingا مختلط MIP) = Mixed Integer Programming ) (و گاهي اوقات كمي غير خطي)، فرموله مي‌شود. سپس با برداشتن محدوديت‌هاي عدد صحيح بودن، يك مسأله آزاد شده به دست آمده و حل مي‌شود. يك جواب خوب (و نه لزوماً بهينه) براي مسأله اصلي مي‌تواند از روند كردن جواب مسأله آزاد شده (براي رسيدن به يك جواب موجه نزديك به جواب مسأله آزاد شده)، به دست آيد؛ اگر چه روند كردن جواب براي رسيدن به يك جواب لزوماً كار آساني نيست، اما در مورد بسياري از مدل‌هاي معمول، به آساني قابل انجام است.

2-1-3- تجزيه

بسياري اوقات آنچه كه حل يك مسأله را از روش‌هاي قطعي بسيار مشكل مي‌كند، اين است كه بيش از يك مورد تصميم‌گيري وجود دارد، مانند موقعيت ماشين‌آلات و تخصيص كار، تخصيص بار به وسائل نقليه و مسيريابي. هر يك از اين موارد تصميم‌گيري ممكن است به تنهايي پيچيده نباشند، اما در نظر گرفتن همه آنها در يك مدل به طور همزمان، چندان آسان نيست. روش ابتكاري تجزيه (Decomposition) مي‌تواند در چنين مسائلي مفيد واقع شود. در اين روش، جواب به دو يا چند بخش (كه فرض مي‌شود از هم مستقل هستند) تجزيه شده و هر يك جداگانه حل مي‌شوند؛ سپس يك روش براي هماهنگ كردن و تركيب اين جواب‌هاي جزيي و به دست آوردن يك جواب خوب ابتكاري، به كار گرفته مي‌شود.

1-2-1-3- تكرار

يكي از روش‌هاي تجزيه، تكرار (Iteration) است. در اين روش، مسأله به زيرمسأله‌هاي جداگانه‌اي تبديل مي‌شود و در هر زمان يكي از زيرمسأله‌ها با ثابت در نظر گرفتن متغيرهاي تصميم موجود در ساير زيرمسأله‌ها در بهترين مقدار شناخته شده‌شان، بهينه مي‌شود؛ سپس يكي ديگر از زيرمسأله‌ها در نظر گرفته مي‌شود و اين عمل به طور متناوب تا رسيدن به يك جواب رضايت‌بخش، ادامه مي‌يابد.

2-2-1-3- روش توليد ستون  (Column Generation)

اين نيز يكي از روش‌هاي تجزيه است كه عموماً براي مسائلي كه داراي عناصر زيادي هستند (مانند مسأله كاهش ضايعات برش با تعداد الگوهاي زياد) كاربرد دارد. در اين روش، حل مسأله به دو بخش تقسيم مي‌شود:

  • يافتن ستون‌ها (يا عناصر) جواب (مثلاً در مسأله كاهش ضايعات برش و يافتن الگوهاي برش).
  • يافتن تركيب بهينه اين عناصر، با توجه به محدوديت‌ها (در مسأله كاهش ضايعات برش و يافتن تركيب مناسب الگوها). يكي از روش‌هاي معمول براي يافتن ستون‌ها، مقدار متغيرهاي دوگانه مسأله اصلي است، اما هر روش ديگري نيز مي‌تواند مورد استفاده قرار گيرد
3-1-3-جستجوي سازنده (Constructive Search)

در اين روش، با شروع از يك جواب تهي، تصميم‌ها مرحله به مرحله گرفته مي‌شود تا يك جواب كامل به دست آيد. هر تصميم، يك تصميم آزمند است؛ يعني قصد دارد با استفاده از اطلاعات به دست آمده از آنچه كه تا كنون انجام شده است، بهترين تصميم را بگيرد.

آنچه كه يك الگوريتم سازنده و يك الگوريتم آزمند را از هم متمايز مي‌كند، نحوه ساختن جواب‌ها مي‌باشد. يك الگوريتم سازنده، جواب را به هر طريق ممكن توليد مي‌كند، اما در يك الگوريتم آزمند، جواب مرحله به مرحله و با توجه به يافته‌ها، ساخته مي‌شود (در هر مرحله، بخشي از جواب ساخته مي‌شود). جستجوي سازنده در مسائلي مانند زمانبندي ماشين و بودجه‌بندي سرمايه كاربرد داشته است. در اينجا مثال مسيريابي كاميون مطرح مي‌شود. در اين مسأله كالا بايد به نقاط مشخصي (هر يك با ميزان مشخصي از تقاضا براي كالا) حمل شود؛ مسأله، سازماندهي اين نقاط در مسيرهاي مشخص با توجه به محدوديت ظرفيت كاميون است.

4-1-3- جستجوي بهبود يافته (Improving Search)

بر خلاف روش جستجوي سازنده، اين روش با جواب‌هاي كامل كار مي‌كند. جستجو  با يك يا چند جواب (مجموعه‌اي از مقادير متغيرهاي تصميم) شروع مي‌شود و در هر مرحله، حركت‌ها يا تغييرات مشخصي در مجموعه فعلي در نظر گرفته مي‌شود و حركت‌هايي كه بيشترين بهبود را ايجاد مي‌كنند، انجام مي‌شود و عمل جستجو ادامه مي‌يابد. يك مسأله در طراحي اين روش، انتخاب جواب اوليه است. گاهي اوقات جواب اوليه يك جواب تصادفي است و گاهي نيز برای ساختن يک جواب اوليه، از روش‌هايي نظير جستجوي سازنده استفاده مي‌شود. مسأله ديگر، تعيين حركت‌ها يا به عبارتي، تعريف همسايگي (مجموعه جواب‌هايي كه با يك حركت از جواب فعلي قابل دسترسي هستند) در مسأله است.

4- روش جستجوي همسايه ( NS= Neighbourhood Search)

استفاده از الگوريتم مبتني بر تكرار مستلزم وجود يك سازوکار توليد جواب است. سازوکار توليد جواب، براي هر جواب i  يك همسايه   به وجود مي‌آورد كه مي‌توان از  i  به آن منتقل شد. الگوريتم‌هاي تكراري به عنوان جستجوي همسايه (NS) يا جستجوي محلي نيز شناخته مي‌شوند. الگوريتم بدين صورت بيان مي‌شود كه از يك نقطه (جواب) شروع مي‌شود و در هر تكرار، از نقطه جاري به يك نقطه همسايه جابه‌جايي صورت مي‌گيرد. اگر جواب همسايه مقدار كمتري داشته باشد، جايگزين جواب جاري مي‌شود (در مسأله حداقل‌سازي) و در غير اين صورت، نقطه همسايه ديگري انتخاب مي‌شود. هنگامي كه مقدار جواب از جواب تمام نقاط همسايه آن كمتر باشد، الگوريتم پايان مي‌يابد.

مفهوم روش جستجوي همسايه از حدود چهل سال پيش مطرح شده است. از جمله اولين موارد آن، كارهاي كرز مي‌باشد كه براي حل مسأله فروشنده دوره‌گرد از مفهوم جستجوی همسايه استفاده کرده است. در كارهاي اخير ريوز نيز جنبه‌هايي از اين شيوه يافت مي‌شود.

اشكالات الگوريتم فوق بدين شرح است:

  • ممكن است الگوريتم در يك بهينه محلي متوقف شود، اما مشخص نباشد كه آيا جواب به دست آمده يك بهينه محلي است يا يك بهينه سراسري.
  • بهينه محلي به دست آمده به جواب  اوليه وابسته است و در مورد چگونگي انتخاب جواب اوليه هيچ راه حلي در دسترسي نيست.
  • به طور معمول نمي‌توان يك حد بالا براي زمان اجرا تعيين كرد.

البته الگوريتم‌هاي مبتني بر تكرار مزايايي نيز دارند؛ از جمله اينكه يافتن جواب اوليه، تعيين مقدار تابع و سازوکار توليد جواب همسايه به طور معمول ساده است.

با وجود آنكه تعيين حد بالاي زمان اجرا امكان‌پذير نيست، ولي با اطمينان مي‌توان گفت كه يك تكرار از الگوريتم در زمان مشخص قابل اجراست.

5-روش‌هاي فرا ابتكاري (Metaheuristic) برگرفته از طبيعت

1-5-معرفي

در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات، «روش‌هاي ابتكاري برگرفته از طبيعت» بوده است؛ اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. كاربرد ‌آنها برگرفته از روش‌هاي ابتكاري پيوسته می‌باشد كه در حل مسائل مشكل تركيبي (NP-Hard) نتايج بسيار خوبی داشته است.

در ابتدا با تعريفي از طبيعت و طبيعي بودن روش‌ها شروع مي‌كنيم؛ روش‌ها برگرفته از فيزيك، زيست‌شناسي و جامعه‌شناسي هستند و به شكل زير تشكيل شده‌اند:

  • استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري
  • استفاده از يك يا چند عامل (نرون، خرده‌ريز، كروموزوم، مورچه و غيره)
  • عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت
  • ايجاد روش‌هاي خود تغييري و خود تبديلي

طبيعت داراي دو تدبير بزرگ مي‌باشد:

  • انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛
  • جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.

به طور كلي دو وضعيت وجود دارد كه در روش‌هاي ابتكاري برگرفته از طبيعت ديده مي‌شود، يكي انتخاب و ديگري جهش. انتخاب ايده‌اي مبنا براي بهينه‌سازي و جهش ايده‌اي مبنا براي جستجوي پيوسته مي‌باشد.

از خصوصيات روش‌هاي ابتكاري  برگرفته از طبيعت، مي‌توان به موارد زير اشاره كرد:

  • پديده‌اي حقيقي در طبيعت را مدل‌سازي مي‌كنند.
  • بدون قطع مي‌باشند.
  • اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.
  • تطبيق‌پذير هستند.

خصوصيات بالا باعث رفتاري معقول در جهت تأمين هوشمندي مي‌شود. تعريف هوشمندي نيز عبارت است از قدرت حل مسائل مشكل؛ بنابراين هوشمندي به حل مناسب مسائل بهينه‌سازي تركيبي منجر می‌شود.

2-5-مسأله فروشنده دوره‌گرد (Travelling Salesman Problem = TSP)

در ابتدا به مسأله فروشنده دوره‌گرد  (TSP)  توجه مي‌كنيم؛ در اين مسأله مأموري به صورت تصادفي در فضاي جستجو (گرافn بعدي) حركت مي‌كند. تنها موقعيت اجباري اين است كه مأمور بايد فهرست شهرهايي را كه رفته به جهت اجتناب از تكرار به خاطر بسپارد. در اين روش بعد از  n حركت، مأمور به شهر شروع باز مي‌گردد و راه‌حلي به دست مي‌آيد. روش جستجوي تصادفي ممكن است تكراري بوده و يا از شهرهاي مختلف شروع شود كه شامل الگوريتم چند شروعه (Multistart) مي‌شود.

روش‌هاي فرا ابتكاري مي‌توانند مطابق موارد زير به دست آيند:

  • استفاده از شيوه‌اي مبتني بر علاقه‌مندي براي انتخاب هر حركت مأمور؛
  • استفاده از روش جستجوي محلي (معاوضه موقعيت گره‌ها) براي بهبودي راه‌حل؛
  • استفاده از روش جستجوي محلي تصادفي و تنها پذيرش تغييرات بهبود يافته؛
  • استفاده از m   مأمور كه از شهرهاي مختلف شروع مي‌كنند.
  • استفاده از تعدادي مأمور با استخدام غير قطعي؛
  • استفاده از روش‌هاي گروهي براي قسمت‌بندي فضا و يا مأموران؛
  • استفاده از قانون پذيرش بدون قطع براي تغييرات اصلاح نشده؛
  • استفاده از اطلاعات آخرين حركات براي اجراي يك سيستم حافظه‌اي.

بهينه‌سازی و معرفي روش‌های آن قسمت 1
بهينه‌سازی و معرفي روش‌های آن قسمت 2
بهينه‌سازی و معرفي روش‌های آن قسمت 3

طرز کار کردن دوربین دیجیتال

مگاپیکسل

فتوسلهای سنسور عکس را پیکسل هم می گویند. اکثر دوربینهای دیجیتال دارای سنسورهایی به اندازه 2/3 تا 2/10 مگاپیکسل هستند. هر چه تعداد پیکسلها بیشتر باشد، عکس دارای جزئیات بیشتری خواهد بود و از این رو می توان آنرا با کیفیت خوب در اندازه بزرگتری چاپ کرد.

سنسورهای عکس در دو مدل CCD و یا CMOS هستند.

از سنسور نوری به کارت حافظه

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

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

انواع مختلف دوربینهای دیجیتال

دستگاه های چند منظوره

دوربینهای دیجیتالی وجود دارند که هم تلفن همراه هستند و هم می توانند موزیک در فرمت MP3 را پخش کنند و هم یک دوربین ویدیویی هستند و به وسیله آنها شما می توانید در اینترنت داخل شوید و یا با آنها یک e-mail بفرستید، و چه کار دیگری از آنها توقع دارید؟ اشکال مختلف دستگاه های کوچک با دوربینهای دیجیتال امروزه در حال گسترش هستند.

دوربینهای اتوماتیک یا کمپکت

اصطلاح کمپکت Compact در مورد دوربینها زمانی مورد استفاده واقع می شود که لنز و بدنه دوربین در یک واحد پیوسته قرار داشته باشند.این نوع دوربینها انواع و اقسام مدلها از کوچک ” ببینید و عکس بگیرید” تا مدلهای بزرگ تر که مانند دوربینهای بزرگ با امکانات اتوماتیک و قابلیت های تنظیم دستی هستند، وجود دارند

دوربینهای پیشرفته دیجیتال

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

استفاده از دوربین

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

قسمتهای مختلف دوربین

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

چشمی یا منظره یاب

خیلی از دوربینهای کمپکت دیجیتال و آنالوگ دارای پنجره کوچکی هستند که فرد عکاس می تواند با دیدن از میان آن کادر و اجزا درون آن ، عکس خود را مشخص نماید.این پنجره کوچک که به چشمی یا منظره یاب دوربین معروف است معمولا” در کنار لنز قرار دارد. چیزی که به عنوان تصویر از درون چشمی دوربین مشاهده می کنید ، تصویری تقریبی از نظر کادر یا عکس نهایی است. اختلاف در تصویر چشمی و تصویر نهایی به خطای پارالکس معروف است.زمانیکه مسئله کادر دقیق سوژه مهم باشد، مثل عکاسی کلوزآپ، صفحه LCD دوربین دیجیتال کمک بزرگی در این مسئله است ، چرا که گیرنده نوری دقیقا” آن چیزی را که می بینید، عکس خواهد گرفت.

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

صفحه LCD

فقط در دوربینهای عکاسی دیجیتال وجود دارد. این نوع چشمی با همکاری لنز دوربین، کادری که در عکس ظاهر خواهد شد را نشان می دهد. با استفاده از صفحه LCD می توان نه تنها متدی را که در بالا در مورد آن شرح دادیم (یعنی فوکوس کردن) را انجام دهید ، بلکه می توانید ببینید که عکس چگونه خواهد افتاد و مثلا” عکس چقدر روشن و یا تیره ظاهر خواهد شد. روی صفحه LCD معمولا” اطلاعات مربوط به تنظیماتی که در هنگام گرفته شدن عکس استفاده خواهند شد، مثل شاتر و اندازه دیافراگم هم نمایش داده می شوند.

در یک دوربین تک لنزی انعکاسی تصویری که درون چشمی آن مشاهده می شود، از درون لنز و یک سری آینه عبور می کند تا به پنجره چشمی در پشت دوربین می رسد. از این رو چشمی این گونه دوربینها ، کادر عکس را دقیقا” نشان داده و بعضی مواقع هم اطلاعات دیگر ، مثل سرعت شاتر و دیافراگم را در آن می توان مشاهده کرد.

شاتر

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

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

دیافراگم

دیافراگم اغلب در لنز جای دارد. اندازه باز بودن دیافراگم همراه با سرعت شاتر، مقدار نوری که به گیرنده نوری می رسد را تنظیم می کنند. رقم پایین تر در دیافراگم به معنی بازتر بودن دیافراگم است. برای هر پله یا گامی که دیافراگم کاهش پیدا می کند ( یعنی رقم ها افزایش پیدا می کنند) مقدار نوری که به داخل دوربین راه پیدا می کند، نصف می شود. دیافراگم 8/2 دو برابر دیافراگم 4 نور به داخل دوربین وارد می کند.

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

لنز

در یک دوربین قطع کوچک که از فیلم mm 36×24 استفاده می کند، یک لنز mm 50 لنزی نرمال به حساب می آید. این لنز نه تصویر را بزرگتر و نه کوچکتر می کند. لنزی که باعث می شود موضوع عکس بزرگتر شود به لنز تله مشهور است که فاصله کانونی آن بیشتر از mm 50 است و اگر موضوع عکس کوچکتر از اندازه طبیعی آن شود، آن لنز ، لنزی واید است. لنزهای با فاصله کانونی متغیر به لنز زوم مشهور هستند.

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

زوم دیجیتال

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

فلاش

حتی دوربینهای کوچک و ساده هم، امروزه مجهز به فلاش هستند. میدان روشن کردن فلاشهای ثابت روی دوربینها محدود است ( بین 5/0 تا 3 متر ، جهت اطلاع دقیق به دفترچه دوربین خود مراجعه کنید) اما این فلاش برای فاصله های کم و کوتاه در یک محیط سربسته کفایت می کند.

کاهش خطر قرمزی چشم

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

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

فلاش حذف سایه ها

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

نور سنجی

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

نورسنجی ماتریسی

در اکثر عکسها نورسنجی بر مبنای کل عکس صورت می گیرد و نور تمام سطح عکس اندازه گیری می شود و نوردهی برای عکس بر مبنای میانگین نور دریافتی انجام می شود. این نوع نورسنجی به نورسنجی چند نقطه ای هم مشهور است.

نورسنجی نقطه ای

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

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

نورسنجی مرکزی

در نورسنجی مرکزی ، نور تمام محوطه اندازه گیری می شود ولی تاکید بیشتر بروی نقطه مرکزی عکس میباشد .

گول خوردن نورسنج دوربین

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

تصحیح یا جبران نوردهی

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

حالت اتوماتیک

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

دوربین دیجیتال چیست؟ قسمت 1
دوربین دیجیتال چیست؟ قسمت 2
دوربین دیجیتال چیست؟ قسمت 3

شناسایی چهره انسان به کمک روش های پردازش تصویر

در تشخیص چهره انسان شما با دیدن تصویر یک فرد باید بگویید که این تصویر مربوط به کدام یک از افرادی است که قبلا دیده‌اید. این مسئله دو بخش دارد:

  • بخش آموزش: در این بخش شما افرادی را که می‌خواهید سیستم بشناسد با تصویر به سیستم می‌دهید.
  • بخش آزمایش: در این بخش اگر تصویری از یکی از افرادی که می‌شناسد را به سیستم بدهیم، سیستم باید او را به درستی به یاد بیاورد.

این مسئله کاربردهای زیادی دارد. برای مثال اگر تعداد افرادی که آموزش می‌دهیم یک فرد باشد، می‌توان از این سیستم به عنوان جایگزین رمز عبور برای رایانه استفاده کرد.

 

 

 

اگر برای مثال تصویر چهره مجرم‌ها را به سامانه آموزش دهیم، می‌توان از دوربین‌های سطح شهر برای پیدا کردن مجرم‌ها استفاده کرد.

 

 

 

کارایی تشخیص چهره علاوه بر کاربردهای مرتبط با تعیین و مقایسه هویت نظیر کنترل دسترسی, امور قضایی, صدور مجوزها و مدارک هویتی و نظارت, در زمینه هایی نظیر تعامل انسان و کامپیوتر, واقعیت مجازی بازیابی اطلاعات از پایگاه های داده, مالتی مدیا و سرگرمی های کامپیوتری به اثبات رسیده است.

یک سیستم تشخیص چهره متداول شامل سه مرحله زیر است:

  1. کشف چهره (Face Detection)
  2. استخراج الگوها (Feature Extraction)
  3. تشخیص چهره (Face Recognition)

چالش های پیش رو

شرایط ثبت تصویر نظیر وضعیت چهره نسبت به دوربین, نورپردازی, حالتهای چهره و تعداد پیکسلها در ناحیه چهره و همچنین روند پیر شدن انسان می تواند تغییرات زیادی را بر چهره انسان تحمیل کند. تغییرات دیگری هم ممکن است از طریق قیافه, پوشش هایی نظیر کلاه یا عینک آفتابی و موی صورت به وجود آید. همچنین افزایش سن, در برخی افراد باعث افزایش یا کاهش وزن می شود.

الگوریتم ها

الگوریتمهای مختلفی برای تشخیص چهره وجود دارند که معمول ترین آنها عبارتند از: PCA – ICA – LFDA – EBGM – SVM – …

الگوریتمی که در این پست مورد بررسی واقع می گردد برای هدف برنامه PCA خواهد بود.

کارهای مرتبط

تا قبل از ارائه ی PCA برای تشخیص چهره, بیشتر کارها روی شناسایی ویژگی های بخشهای صورت مانند چشمها, بینی, دهان و … و تعریف روابط بین این اعضا متمرکز بود. اما تحقیقات روی قدرت انسان در تشخیص چهره نشان داد که ویژگی های اعضای منفرد صورت و ارتباطات لحظه ای بین آنها برای شناخت مناسب چهره کافی نیست.

در سال 1966 Bledsoe اولین کسی بود که یک روش نیمه اتوماتیک برای تشخیص چهره ارائه کرد. در این روش چهره ها بر اساس ویژگی هایی که به وسیله ی انسان علامت زده شده بود دسته بندی می شدند. اندکی بعد با کارهای انجام شده در آزمایشگاههای Bell, یک بردار با بیش از 21 ویژگی (مانند عرض دهان, ضخامت لبها و …) تو سعه داده شد. ویژگی های انتخاب شده عمدتاً حاصل ارزیابی های ذهن انسان بودند و پیاده سازی آنها کار مشکلی بود.

در سال 1989, Kirby و Sirovich یک روش جبری برای محاسبه ساده ی eigenface ها ارائه کردند.

در سال 1991 , Turk و Pentland اثبات کردند که خطای مانده هنگام کدینگ eigenface ها می تواند برای دو منظوراستفاده شود:

  1. تشخیص وجود چهره در یک عکس
  2. تعیین محل تقریبی چهره در عکس

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

در مقاله ای از Rajkiran Gottumukkal, Vijayan K.Asari روشی به نام Modular PCA ارائه شده است. با مقایسه ی این روش با روش PCA متداول, مشخص می شود که این روش با وجود تغییرات زیادی در جهت تابش نور وحالت چهره, نرخ بازشناسی بیشتری نسبت به PCA دارد. در این روش عکسها به چند قسمت کوچکتر تقسیم می شوند و PCA روی هرکدام از این قطعات به طور جداگانه اعمال می شود. این موضوع باعث می شود که تغییرات چهره از جمله تغییر در جهت تابش نور و حالت چهره, باعث تغییر ویژگی های موضعی چهره یک فرد نشود.

در مقاله ای از  Trupti M. Kodinariya با ترکیب الگوریتم PCA با چند الگوریتم دیگر یک روش ترکیبی ارائه شده است.

در این مقاله سیستم تشخیص چهره در دو حالت کار می کند : تمرین و دسته بندی :

حالت تمرین شامل نرمال سازی و استخراج ویژگی از تصاویر با استفاده از الگوریتم PCA, ICA می باشد. . سپس ویژگی های استخراج شده, با استفاده از BPNN ها (back propagation neural network) تمرین داده می شوند تا فضای ویژگی ها به کلاسهای متفاوت دسته بندی شوند.

در حالت دسته بندی,عکسهای جدید به نتایج حاصل از حالت تمرین اضافه می شوند. یک روش ترکیب کننده, روی نتایج بخش تمرین اعمال می شوند تاعکسهای جدید برحسب کلاسهای ایجاد شده دسته بندی شوند.

در مقاله ای از احمد محمودی, روشی با نام PCA چند لایه ارائه شده است. در این روش برای محاسبه ی مولفه های اصلی از یک شبکه عصبی خطی استفاده شده است, که علاوه بر کاهش حجم مورد نیاز برای محاسبات, طراحی سخت افزار آن بسیارساده تر خواهد بود. همچنین با توجه به قابلیت های شبکه عصبی در پردازش موازی, سرعت انجام محاسبات افزایش چشم گیری داشته است.

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

در مقاله ای از داود ساریخانی, روشی با استفاده از الگوریتم های PCA, LDA و شبکه های عصبی پیشنهاد شده است.روش ارایه شده دارای چهارقسمت پردازشی زیراست:

  1. بخش پیش پردازش شامل یکنواخت سازی هیستوگرام و نرمالیزه کردن تصاویر
  2. بخش کاهش بعد فضا به کمک PCA
  3. استخراج ویژگیها با استفاده از LDA برای جداسازی کلاس ها و تفکیک پذیری چهره ها
  4. استفاده از شبکه عصبی به منظور طبقه بندی چهره ها و اعلام هویت چهره

الگوریتم Principal Component Analysis) PCA):

این روش در سال 1991 توسط Turk و Pentland پیشنهاد شد که از تحلیل المانهای اصلی یا همان PCA برای کاهش بعد استفاده کرده‎ تا بتواند زیرفضایی با بردارهای متعامد پیدا کند که در آن زیرفضا پراکندگی داده ها را به بهترین حالت نشان دهد. این زیرفضا را هنگامی که بر روی داده های چهره اعمال شوند، فضای چهره میگویند. پس از مشخص شدن بردارها تمامی تصاویر به این زیر فضا منتقل می‏‏شوند تا وزنهایی که بیانگر تصویر در آن زیرفضا هستند بدست آیند. با مقایسه شباهت وزنهای موجود با وزن تصویر جدیدی که به این زیر فضا منتقل شده می‏‏توان تصویر ورودی را شناسایی کرد.

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

در این روش یک تصویر با ابعاد n*m به یک بردار با nm مولفه تبدیل می شود. یعنی می توان عکس را به صورت نقطه ای در فضای nm بعدی تصور کرد.
هدف PCA یافتن بردارهایی است که به بهتر ین نحو ممکن کار شناسایی ز یر فضا را انجام دهند. این بردارها فضای چهره را تعریف می کنند. از آن جایی که این بردارها، بردار ویژه ی ماتر یس همبستگی مربوط به تصاویر چهره می باشند و همچنین به دلیل شباهت به چهره یانسان، آن ها را eigenface می نامند.

محاسبه ی eigenface ها

اگر مجموعه ی عکس های ورودی را ماتریسهای

 

در نظر بگیریم, میانگین چهره ها به صورت زیر محاسبه می شود:

 

البته همان طور که در بخش قبل گفته شد در این روش یک تصویر با ابعاد n*m به یک بردار با nm مولفه تبدیل می شود. یعنی ما یک عکس را به صورت یک بردار سطری یا ستونی با nm مولفه در نظر می گیریم. تمامی فرمول های ذکر شده در این الگوریتم با این فرض است که ماتریس تصویر را به صورت یک بردار ستونی درنظر گرفته ایم.

 

 

تفاوت هر تصویر از میانگین به صورت زیر محاسبه می شود:

 

بردار Uk به نحوی انتخاب می شود که مقدار λk ماکزیمم شود:

 

البته با فرض زیر:

 

بردارهای Uk و λk به ترتیب بردارهای ویژه و مقادیر ویژه ی ماتریس همبستگی می باشند.ماتریس همبستگی از رابطه ی زیر محاسبه می شود :

 

 

یعنی می توان با استفاده از ماتریس کوواریانس نیز به بردار و مقدار ویژه رسید.

بردار U همان بردار eigenface میباشد. نمونه ای از آنرا در تصویر زیر مشاهده می کنید :

 

 

 

همان طور که مشاهده می کنید, بردار ویژه در واقع شامل عکسهایی با همان ابعاد عکس های ورودی می باشد که شبیه به شبح هستند.

بخش تشخیص چهره

برای تشخیص اینکه یک عکس جدید مربوط به کدام یک از عکسهایی که سیستم با آن تمرین داده شده است, می باشد باید تمام عکسهایی که سیستم با آن تمرین داده شده است و همچنین عکس جدید را به فضای چهره نگاشت کنیم.
اگر هر یک از این عکسها را Γ بنامیم آنگاه طبق فرمول زیر می توان عکس را به فضای چهره نگاشت کرد:

 

سپس بردار وزنها را تشکیل می دهیم:

 

حالا می توانیم تعیین کنیم که عکس ورودی متعلق به کدام کلاس است. یکی از راههایی که برای این کار وجود دارد این است که بردار وزنهای عکس ورودی را با بردار وزنهای عکسهایی که قبلاً به سیستم آموزش داده شده بودند مقایسه کنیم. برای این کار می توانیم از فاصله ی اقلیدسی مانند زیر استفاده کنیم :

 

یعنی ما به تعداد عکسهایی که سیستم با آن تمرین داده شده اند, ϵ داریم.
اگر مقدار ϵ از یک مقدار از پیش تعیین شده کمتر بود, آنگاه تصویر ورودی یک تصویر شناخته شده است.اگر بیشتر بود و از یک مقدار دوم کمتر بود آنگاه تصویر ورودی یک شخص ناشناس است. اما اگر از هر دو مقدار بزرگتر بود تصویر ورودی چهره نیست!
اما پس از تشخیص اینکه تصویر ورودی یک تصویر شناخته شده است, برای اینکه تشخیص بدهیم که این عکس مربوط به چه کسی است باید مقدار ϵ ها را با هم مقایسه کنیم. بدیهی است که عکس ورودی مربوط به عکسی است که فاصله ی آنها (ϵ) کمتر از سایر عکسها باشد.

بهبود محاسبه ی بردارهای ویژه ی ماتریس کوواریانس

فرض کنید n عکس با اندازه ی xy داریم. پس از تغییر شکل عکسها به یک بردار, اندازه ی ماتریس شامل بردارها, nxy خواهد بود. پس از بدست آوردن اختلاف هر عکس با میانگین عکس ها, بردار A با اندازه یnxy به وجود می آید.
طبق رابطه ی کوواریانس, اندازه ی ماتریس کوواریانس xyxy خواهد بود. برای درک این اندازه, فرض کنید که ابعاد عکس ورودی, 100×100 پیکسل باشد. طبق محاسبات بالا اندازه ی ماتریس کوواریانس 10000×10000 خواهد بود. یعنی باید 100 میلیون نقطه را ذخیره کرد که این کار به حدود 0.8 گیگا بایت حافظه نیاز دارد! درضمن محاسبه ی یک ماتریس با این حجم به زمان زیادی نیز نیاز دارد.

برای حل این مشکل از یک قضیه ی ریاضی استفاده می کنیم. این قضیه بیان می کند که بردارهای ویژه ی ماتریس AAT با بردارهای ویژه ی ماتریس ATA یکسان است. یعنی ما می توانیم از ماتریسATA استفاده کنیم که یک ماتریس nn (n تعداد عکسهای ورودی است) می باشد و حجم محاسبات آن به شدت کمتر از یک ماتریس xyxy می باشد.

آزمایش‌ها

برای آزمایش این سیستم نیاز به یک مجموعه عکس استاندارد داریم. برای این کار از مجموعه داده یAT&T متعلق به دانشگاه کمبریج استفاده می کنیم. این مجموعه عکس شامل عکسهای 40 فرد و از هر فرد 10 عکس مختلف می باشد. یعنی در مجموع شامل 400 عکس می باشد.

آزمایش اول: کد مربوط به این بخش را می توانید از اینجا دریافت کنید.
برای آزمایش 25 عکس از این مجموعه انتخاب می کنیم:

 

 

همانطور که توضیح داده شد یکی از مراحل الگوریتم محاسبه ی میانگین تصاویر وروری است. میانگین 25 تصویر بالا را در عکس زیر می بینید:

 

 

بردارهای ویژه (eigenface) ی بدست آمده از عکسهای بالا را در تصویر زیر می بینید:

 

 

برای آزمایش نرخ تشخیص چهره, 25 عکس جدید که مربوط به همان افرادی می شدند که در بالا مشاهده کردید به سیستم داده شد. که حدود 50 درصد از آنها به درستی شناسایی شدند که با توجه به اینکه از هر فرد تنها یک عکس برای تمرین به سیستم داده شده بود, قابل قبول به نظر می رسد.

اما یکی از کارهایی که باعث می شود نرخ تشخیص چهره افزایش پیدا کند, مطمئناً تمرین دادن سیستم با عکس های بیشتر است. به این معنی که ما از هر فرد, چند عکس مختلف به سیستم بدهیم و سیستم فضای چهره را با استفاده از این عکس ها ایجاد کند. کد پیاده سازی شده برای این بخش را می توانید از اینجا دریافت نمایید.
برای آزمایش نرخ تشخیص چهره با این روش, 6 عکس از 25 مجموعه عکس (هر مجموعه متعلق به چهره ی یک فرد) از مجموعه داده ی AT&T, یعنی در مجموع 150 عکس, به سیستم داده شد, تا سیستم با آنها تمرین داده شود. سپس 25 عکس مربوط به همان افرادی که سیستم با عکس آنها تمرین داده شده بود, برای تشخیص به سیستم داده شد که 84 درصد از آنها به درستی شناسایی شدند. مشاهده می شود که نرخ تشخیص چهره نسبت به زمانی که از هر فرد فقط یک عکس برای تمرین به سیستم داده شده بود, بیش از 30 درصد افزایش یافته است.

 

تشخیص چهره انسان به کمک پردازش تصویر قسمت 1
تشخیص چهره انسان به کمک پردازش تصویر قسمت 2

روش جستجوی تکاملی

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

نظریه تکامل

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

انواع مختلف الگوریتم‌های تکاملی

انواع مختلف الگوریتم‌های تکاملی که تا بحال مطرح شده‌اند، به شرح زیر می‌باشد:

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

الگوریتم تکاملی

Evolutionary Strategies

Evolutionary Programming

Differential Evolution

Cultural Evolution

هم‌فرگشتی

کدگذاری و نحوه نمایش

نحوه نمایش جواب مسئله و ژن‌ها در موفقیت الگوریتم و نحوه پیاده‌سازی الگوریتم ژنتیک تأثیر بسیار مهمی دارد. در بیشتر مسائل نیز روش‌های مختلفی برای نشان دادن جواب مسئله می‌توان طراحی کرد.

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

یکی از مسائل کلاسیک در الگوریتم‌های ژنتیک مسئله ۸ وزیر است. ماهیت مسئله به گونه‌ای است که مدلسازی آن و همچنین اعمال عملگرهای الگوریتم ژنتیک بر روی آن بسیار ساده است. همچنین علاوه برای الگوریتم ژنتیک، روش الگوریتم تبرید شبیه‌سازی شده نیز در ساده‌ترین شکل خود برای مسئله چند وزیر نیز روش مناسبی هست همچنین از مسائل مهم دیگری که با استفاده از این الگوریتم قابل حل می‌باشد مسئلهٔ فروشندهٔ دوره‌گرد یا مسئلهٔ چیدمان دینامیک می‌باشد.

فلو چارت این الگوریتم

شمای کلی سودوکوی الگوریتم

منبع

 

برای استفاده از یک الگوریتم ژنتیک، جمعیتی از افراد در داخل یک فضای جستجو حفظ می شود. هر کدام از این افراد در واقع یک راه حل ممکن برای مسئله مطرح شده هستند. هر عضو با برداری با طول محدود از اجزا یا متغیر ها و با کمک حروف الفبای خاصی کدگذاری می شود. این حروف الفبای خاص معمولا الفبای باینری  هستند. برای ادامه دادن شباهت این روش با اصول ژنتیکی، هر کدام از اعضا به عنوان کروموزوم تعبیر می شوند و متغیر ها مشابه ژن ها در نظر گرفته می شوند. پس یک کروموزوم ( یک جواب برای مسئله)، از چند ژن (متغیر ها) تشکیل شده است. برای نشان دادن توانایی های هر یک از اعضا برای رقابت با دیگر اعضای جمعیت، به هر کدام از جواب های ممکن یک امتیاز برازندگی اختصاص داده می شود.
عضوی که دارای امتیاز برازندگی بهینه ( یا به طور کلی تر نزدیک به بهینه) است دلخواه ما می باشد. هدف الگوریتم ژنتیک، استفاده از “پرورش” انتخابی جواب ها، برای ایجاد فرزندانی بهتر از والدین به کمک ترکیب کردن اطلاعات کروموزوم ها است.

الگوریتم ژنتیک قسمت 1
الگوریتم ژنتیک قسمت 2

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

چکیده : با توجه به پیشرفت های اخیر فناوری ارتباطات بی سیم در چند دهه اخیر ، مطالعات کارشناسان در زمینه شبکه های گیرنده بی سیم هم سیر صعودی را طی کرده است.بسیاری از این بررسی ها در قالب کتب علمی ، الحاقیه ، الگوریتم و موارد کاربردی اجرا و اعمال شده اند. کارایی این شبکه ها به طور مستقیم به پروتکل های مسیریابی که روی زمان زندگی شبکه تآثیر می گذارند بستگی خواهد داشت. خوشه بندی یکی از رایج ترین روش های اجرایی در این مبحث تلقی می شود. ما در این مقاله به بررسی کارایی انرژی در پروتکل های بر پایه الگوریتم های کندوی زنبور عسل می پردازیم که نشان دهنده امتداد طول عمر شبکه می باشد. الگوریتم های کندوی زنبور عسل طوری طراحی شده اند که رفتارهای جستجوگرانه زنبورهای عسل را شبیه سازی کرد و به طور موفقیت آمیزی در تکنیک های خوشه بندی مورد استفاده قرار می گیرند. عملکرد این روش پیشنهادی با پروتکل های متکی بر LEACH و بهینه سازی گروهی اجزا که پیش از این مورد بررسی قرار گرفته اند ،مقایسه می شود. نتایج این بررسی ها نشان می دهد که الگوریتم های کندوی زنبور عسل میتواند در پروتکل های مسیریابی WSN روند موفقیت آمیزی داشته باشد.
کلمات کلیدی : شبکه های گیرنده بی سیم ، برپایه خوشه بندی ( خوشه ای ) ، الگوریتم زنبور عسل فایل PDF – در 22 صفحه
– نویسنده : ناشناس
دانلود
پسورد فایل : behsanandish.com


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

 

شامل سرفصل های :

1- الگوریتم کلونی زنبورعسل مصنوعی

2- معرفی چند الگوریتم بهینه شده کلونی زنبورعسل در محیط پیوسته

3- الگوریتم کلونی زنبورعسل مصنوعی موازی

4- الگوریتم کلونی زنبورعسل مصنوعی برای مسائل بهینه سازی دودویی

فایل Power Point – در 40 اسلاید – نویسنده : ناشناس

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

پسورد فایل : behsanandish.com


رویکرد الگوریتم فرا ابتکاری کلونی زنبور عسل مصنوعی برای تعیین مکان بهینه سوئیچها در شبکه ارتباطی تلفن همراه

چكيده : در این تحقیق برای حل مسئله ی تخصیص سلول به سوئیچ (CTSAP) ، از الگوریتم فراابتکاری کلونی زنبور عسل مصنوعی (ABC) استفاده شده است. هدف مسئله، تخصیص بهینه سلولها به سوئیچها با حداقل هزینه است. در این تحقیق هزینه از دو جزء تشکیل یافته است. یکی هزینه ی تعویضها که مربوط به دو سوئیچ است و دیگری هزینه ی اتصال میباشد. ظرفیت پاسخگویی تماس هر سوئیچ نیز محدود است و فرض میشود همه ی سوئیچها ظرفیت برابری داشته باشند. در مدل این پژوهش هر سلول باید فقط و فقط تنها به یک سوئیچ متصل گردد(single homed).مدل ریاضی این تحقیق، غیرخطی صفر و یک است.  کد رایانه ای الگوریتم با نرم افزار MATLAB 7.8.0 نوشته شده است. پس از تعیین مقادیر پارامترهای مدل و تأیید صحت عملکرد کد و تنظیم پارامترهای کنترل، کارایی الگوریتم با ایجاد مسائل آزمایشی، با یکی از بهترین الگوریتمهای CTSAP یعنی الگوریتم بهینه سازی کلونی مورچگان (ACO) مقایسه شده است و نتایج نشان می دهد که الگوریتم ABC در قیاس با ACO عملکرد رضایت بخشی دارد.
واژگان کليدی: مسئله تخصیص سلول به سوئیچ، الگوریتم فراابتکاری، شبکههای تلفن همراه، الگوریتم کلونی زنبور عسل مصنوعی
فایل PDF – در 24 صفحه- نویسندگان : سيد محمد علی خاتمی فيروزآبادی , امين وفادار نيكجو
دانلود
پسورد فایل : behsanandish.com


ﮐﻠﻮﻧﯽ زﻧﺒﻮرﻫﺎي ﻣﺼﻨﻮﻋﯽ ﺳﻠﻮﻟﯽ

ﭼﮑﯿﺪه: در اﯾﻦ ﻣﻘﺎﻟﻪ دو ﻣﺪل ﺗﺮﮐﯿﺒﯽ ﮐﻪ از ﺗﺮﮐﯿﺐ ﮐﻠﻮﻧﯽ زﻧﺒﻮرﻫـﺎ و اﺗﻮﻣﺎﺗﺎي ﺳﻠﻮﻟﯽ ﺣﺎﺻﻞ ﺷﺪه اﺳﺖ ﺑﻪ ﻣﻨﻈﻮر ﺑﻬﯿﻨﻪ ﺳﺎزي ﭘﯿﺸﻨﻬﺎد ﻣﯽﮔﺮدد . اﺗﻮﻣﺎﺗـﺎي ﺳـﻠﻮﻟﯽ وﻇﯿﻔـﻪ ﮐـﺎﻫﺶ آﻧﺘﺮوﭘـﯽ و اﻓـﺰاﯾﺶ ﺳـﺮﻋﺖ ﻫﻤﮕﺮاﯾﯽ را ﺑﻪ ﻋﻬﺪه دارد . در ﻣـﺪل ﭘﯿﺸـﻨﻬﺎدي در اول ﻫـﺮ ﺳـﻠﻮل از اﺗﻮﻣﺎﺗﺎي ﯾﺎدﮔﯿﺮ ﺳﻠﻮﻟﯽ ﯾﮏ ﮐﻠﻮﻧﯽ از زﻧﺒﻮرﻫـﺎ ﻗـﺮار داده ﻣـﯽ ﺷـﻮد . ﺑـﻪ ﺑﺪﺗﺮﯾﻦ ﻫﺮﺳﻠﻮل ، ﻣﻨﻈﻮر ﺑﻬﺒﻮد ﺟﺴﺘﺠﻮي ﺳﺮاﺳﺮي و ﻫﻤﮕﺮاﯾﯽ ﺳﺮﯾﻌﺘﺮ ﺑﺎ ﺑﻬﺘﺮﯾﻦ ﻫﻤﺴﺎﯾﮕﺎن ﺑﻪ روش ﺣﺮﯾﺼﺎﻧﻪ ﺟﺎﯾﮕﺰﯾﻦ ﻣﯽ گردد. در ﻣﺮﺣﻠـﻪ دوم در ﻫﺮ ﺳﻠﻮل ﯾﮏ زﻧﺒﻮر ﻗﺮار ﻣـﯽ ﮔﯿـﺮد .ﻧﺘـﺎﯾﺞ آزﻣﺎﯾﺸـﻬﺎ ﺑـﺮ روي ﻣﺴﺎیل ﻧﻤﻮنه ﻧﺸﺎن ﻣﯿﺪﻫﺪ ﮐﻪ روش ﻫﺎی اراﺋﻪ ﺷﺪه از ﻋﻤﻠﮑﺮد ﺑﻬﺘـﺮي در ﻣﻘﺎﯾﺴﻪ ﺑﺎ ﻣﺪل ﮐﻠﻮﻧﯽ زﻧﺒﻮرﻫﺎي ﻣﺼﻨﻮعی اﺳﺘﺎﻧﺪارد ﺑﺮﺧﻮردار می باشد.
واژه ﻫﺎي ﮐﻠﯿﺪی : کلونی زنبور، اﺗﻮﻣﺎﺗﺎي ﺳﻠﻮﻟﯽ، بهینه سازی
فایل PDF – در 4 صفحه- نویسندگان : زهرا گل میرزایی ، محمدرضا میبدی
دانلود
پسورد فایل : behsanandish.com


یک بررسی جامع: الگوریتم و برنامه های کاربردی کلونی زنبور عسل (ABC)

A comprehensive survey: artificial bee colony (ABC) algorithm and applications

Abstract : Swarm intelligence (SI) is briefly defined as the collective behaviour of decentralized
and self-organized swarms. The well known examples for these swarms are bird
flocks, fish schools and the colony of social insects such as termites, ants and bees. In 1990s,
especially two approaches based on ant colony and on fish schooling/bird flocking introduced
have highly attracted the interest of researchers. Although the self-organization features are
required by SI are strongly and clearly seen in honey bee colonies, unfortunately the researchers
have recently started to be interested in the behaviour of these swarm systems to describe
new intelligent approaches, especially from the beginning of 2000s. During a decade, several
algorithms have been developed depending on different intelligent behaviours of honey bee
swarms. Among those, artificial bee colony (ABC) is the one which has been most widely
studied on and applied to solve the real world problems, so far. Day by day the number of
researchers being interested in ABC algorithm increases rapidly. This work presents a comprehensive
survey of the advances with ABC and its applications. It is hoped that this survey
would be very beneficial for the researchers studying on SI, particularly ABC algorithm.
,Keywords : Swarm intelligence
,Bee swarm intelligence
Artificial bee colony algorithm

فایل Power Point - در 37 صفحه - نویسندگان: Dervis Karaboga , Beyza Gorkemli , Celal Ozturk , Nurhan Karaboga
A comprehensive survey- artificial bee colony (ABC)
پسورد فایل : behsanandish.com


الگوریتم جستجوی کلونی زنبور عسل مصنوعی جهانی برای بهینه سازی تابع عددی

Global Artificial Bee Colony Search Algorithm for Numerical Function Optimization

Abstract—The standard artificial bee colony (ABC) algorithm as a relatively new swarm optimization method is often trapped in local optima in global optimization. In this paper, a novel search strategy of main three procedures of the ABC algorithm is presented. The solutions of the whole swarm are exploited based on the neighbor information by employed bees and onlookers in the ABC algorithm. According to incorporating all employed bees’ historical best position information of food source into the solution search equation, the improved algorithm that is called global artificial bee colony search algorithm has great advantages of convergence property and solution quality. Some experiments are made on a set of benchmark problems, and the results demonstrate that the proposed algorithm is more effective than other population based optimization algorithms. Keywords—Artificial bee colony, Search strategy, Particle swarm optimization, Function optimization فایل PDF – در 4 صفحه – نویسندگان : Guo Peng, Cheng Wenming, Liang Jian Global Artificial Bee Colony Search Algorithm for Numerical Function Optimization پسورد فایل : behsanandish.com


یک الگوریتم کلونی زنبور عسل مصنوعی اصلاح شده برای بهینه سازی مسائل محدود شده

A modified Artificial Bee Colony (ABC) algorithm for constrained optimization problems

Abstract : Artificial Bee Colony (ABC) algorithm was firstly proposed for unconstrained optimization problems on where that ABC algorithm showed superior performance. This paper describes a modified ABC algorithm for constrained optimization problems and compares the performance of the modified ABC algorithm against those of state-of-the-art algorithms for a set of constrained test problems. For constraint handling, ABC algorithm uses Deb’s rules consisting of three simple heuristic rules and a probabilistic selection scheme for feasible solutions based on their fitness values and infeasible solutions based on their viola- tion values. ABC algorithm is tested on thirteen well-known test problems and the results obtained are compared to those of the state-of-the-art algorithms and discussed. Moreover, a statistical parameter analysis of the modified ABC algorithm is conducted and appropriate values for each control parameter are obtained using analysis of the variance (ANOVA) and analysis of mean (ANOM) statistics. Keywords: Swarm intelligence Modified Artificial Bee Colony algorithm Constrained optimization فایل PDF – در 37 صفحه – نویسندگان : Dervis Karaboga , Bahriye Akay A modified Artificial Bee Colony (ABC) algorithm for constrained optimization1 پسورد فایل : behsanandish.com


 یک الگوریتم کلونی زنبور عسل مصنوعی جدید-بر اساس فاصله داده های سریال با استفاده گرام های سیگما
ABC-SG: A New Artificial Bee Colony Algorithm-Based Distance of Sequential Data Using Sigma Grams

Abstract 
The problem of similarity search is one of the main
problems in computer science. This problem has many
applications in text-retrieval, web search, computational
biology, bioinformatics and others. Similarity between
two data objects can be depicted using a similarity
measure or a distance metric. There are numerous
distance metrics in the literature, some are used for a
particular data type, and others are more general. In this
paper we present a new distance metric for sequential data
which is based on the sum of n-grams. The novelty of our
distance is that these n-grams are weighted using artificial
bee colony; a recent optimization algorithm based on the
collective intelligence of a swarm of bees on their search
for nectar. This algorithm has been used in optimizing a
large number of numerical problems. We validate the new
distance experimentally.
Keywords:  Artificial Bee Colony, Extended Edit
Distance, Sequential Data, Distance Metric, n-grams. 
فایل PDF – در 7 صفحه – نویسنده :Muhammad Marwan Muhammad Fuad
پسورد فایل : behsanandish.com

کاربرد الگوریتم کلونی زنبور عسل مصنوعی در جستجوی آزادسازی بهینه سد بزرگ آسوان

Application of artificial bee colony (ABC) algorithm in search of optimal release of Aswan High Dam

Abstract. The paper presents a study on developing an optimum reservoir release policy by using ABC algorithm. The decision maker of a reservoir system always needs a guideline to operate the reservoir in an optimal way. Release curves have developed for high, medium and low inflow category that can answer how much water need to be release for a month by observing the reservoir level (storage condition). The Aswan high dam of Egypt has considered as the case study. 18 years of historical inflow data has used for simulation purpose and the general system performance measuring indices has measured. The application procedure and problem formulation of ABC is very simple and can be used in optimizing reservoir system. After using the actual historical inflow, the release policy succeeded in meeting demand for about 98% of total time period. فایل PDF – در 8 صفحه – نویسندگان : Md S Hossain and A El-shafie  Application of artificial bee colony (ABC) algorithm پسورد فایل : behsanandish.com


الگوریتم بهینه سازی کلونی زنبور عسل مصنوعی برای حل مشکلات بهینه سازی محدود

Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems

Abstract. This paper presents the comparison results on the performance of the Artificial Bee Colony (ABC) algorithm for constrained optimization problems. The ABC algorithm has been firstly proposed for unconstrained optimization problems and showed that it has superior performance on these kind of problems. In this paper, the ABC algorithm has been extended for solving constrained optimization problems and applied to a set of constrained problems . فایل PDF – در 10 صفحه – نویسندگان : Dervis Karaboga and Bahriye Basturk Artificial Bee Colony (ABC) Optimization پسورد فایل : behsanandish.com


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

Artificial Bee Colony Algorithm and Its Application to Generalized Assignment Problem

فایل PDF – در 32 صفحه – نویسندگان : Adil Baykasoùlu, Lale Özbakır and Pınar Tapkan Artificial Bee Colony Algorithm and Its پسورد فایل : behsanandish.com


  الگوریتم کلونی زنبور عسل مصنوعی
Artificial Bee Colony Algorithm

Contents 
• Swarm Intelligence – an Introduction 
• Behavior of Honey Bee Swarm 
 • ABC algorithm
 • Simulation Results 
• Conclusion 
فایل PDF از یک فایل Power Point – در 22 اسلاید- نویسنده : ناشناس
پسورد فایل : behsanandish.com

بهینه سازی کلونی زنبور عسل پارت 1: مرور الگوریتم

BEE COLONY OPTIMIZATION PART I: THE ALGORITHM OVERVIEW

,Abstract: This paper is an extensive survey of the Bee Colony Optimization (BCO) algorithm proposed for the first time in 2001. BCO and its numerous variants belong to a class of nature-inspired meta–heuristic methods, based on the foraging habits of honeybees. Our main goal is to promote it among the wide operations research community. BCO is a simple, but ecient meta–heuristic technique that has been successfully applied to many optimization problems, mostly in transport, location and scheduling fields. Firstly, we shall give a brief overview of the meta–heuristics inspired by bees’ foraging principles, pointing out the dierences between them. Then, we shall provide the detailed description of the BCO algorithm and its modifications, including the strategies for BCO parallelization, and give the preliminary results regarding its convergence. The application survey is elaborated in Part II of our paper. Keywords: Meta–heuristics, Swarm Intelligence, Foraging of Honey Bees فایل PDF- در24 صفحه – نویسندگان : Tatjana DAVIDOVI´ C , Duˇsan TEODOROVI´ C , Milica ˇSELMI´ C BEE COLONY OPTIMIZATION PART I پسورد فایل : behsanandish.com


مثال (۲) : بهبود کارایی الگوریتم سیستم ایمنی مصنوعی در مسائل بهینه‌سازی

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

در مثال ارائه شده جواد‌زاده و میبدی تلاش در تقویت الگوریتم‌های سیستم ایمنی مصنوعی با استفاده از استراتژی ترکیب دارند. بدین صورت که از یک هیوریستیک جستجوی محلی در آنتی‌بادی های حافظه استفاده می‌شود.

ترکیب الگوریتم سیستم ایمنی مصنوعی و جستجوی محلی

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

جهت بهبود دقت الگوریتم از روش جستجوی محلی در ناحیه آنتی بادی سلول های حافظه استفاده شده است. علت نامگذاری جستجو به جستجوی محلی ، انجام جستجو فقط در اطراف آنتی بادی سلول های حافظه در مقیاس کوچک می باشد. بنابراین با جستجوی محلی در ناحیه آنتی بادی های سلول های حافظه با مقیاس کوچک در اطراف بهترین آنتی بادی سلول های حافظه ، دقت الگوریتم افزایش یافته و شایستگی های آنتی بادی های سلول های حافظه افزایش یافته و بر سرعت همگرایی افزوده می شود.
جوادزاده و میبدی برای جستجوی محلی از جستجوی تپه نوردی و الگوریتم های ژنتیک استفاده نموده اند. در مسائلی که ابعاد فضای مسئله کوچک باشد جستجوی تپه نوردی دقت بالایی دارد و با بالا رفتن ابعاد فضای مسئله ، زمان اجراء به صورت نمایی افزایش می یابد. الگوریتم پیشنهادی به صورت زیر می باشد.

Code New Algorithm

 

در ادامه روند الگوریتم ، پس از بهبود آنتی بادی های سلول های حافظه ، علاوه بر اضافه نمودن تعداد آنتی بادی ها به صورت تصادفی به جمعیت آنتی بادی ها ، بخشی از آنتی بادی های حافظه برای افزایش سرعت همگرایی به جمعیت آنتی بادی ها افزوده می شود. برای اعمال عملگر ابرجهش از رابطه های (۷) و (۸) و برای تعیین اندازه جمعیت برای n آنتی بادی از رابطه (۹) استفاده شده است.

روابط 7 و8

 

 

 

 

در رابطه (۷) متغیر c’ تعداد آنتی بادی هایی است که تحت تاثیر عملگر ابرجهش قرار گرفته اند. و (N(0,1 عدد تصادفی تابع گوسین با میانگین صفر و انحراف معیار δ=1 می باشد.
در رابطه (۸) پارامتر β، پارامتری برای کنترل ضریب کاهش تابع نمایی و *f مقدار شایستگی است که در بازه [۰,۱] نرمال شده است.

روابط 9

 

 

 

در رابطه (۹) متغیر Nc مجموع اعضاء جمعیت تولید شده برای آنتی بادی ها، ضریب تکثیر، N تعداد آنتی بادی ها و ()round عملگری است که آرگومان ورودی خود را به نزدیکترین عدد گرد می نماید.

نتایج آزمایش ها

در این قسمت شبیه سازی راهکار پیشنهادی برای چهار تابع محک استاندارد یعنی روابط (۱۰) تا (۱۳) به ازاء کیفیت جواب بدست آمده بر اساس روش های مختلف جستجوی محلی توسط جوادزاده و میبدی مورد مطالعه قرار گرفته است.

روابط 10و11و12

 

 

 

 

 

 

روابط 13

 

جهت ارزیابی راهکارهای پیشنهادی (بجز در مورد جستجوی محلی تپه نوردی) توابع مورد آزمایش به صورت سی بُعدی و آنتی بادی ها به صورت اعداد حقیقی استفاده شده و راهکار پیشنهادی با ۱۰۰ بار تکرار برای بدست اوردن پاسخ بهینه مورد آزمون قرار گرفتند.

راهکار پیشنهادی با جستجوی محلی تپه نوردی

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

جواد زاده و میبدی در ادامه برای مطالعه روند همگرایی راهکار پیشنهادی با جستجوی محلی تپه نوردی ، بهترین ، بدترین ، میانگین و انحراف معیار ارزش تمام آنتی بادی های حافظه برای تمام توابع (روابط ۱۰ تا ۱۳) را آزمایش نموده اند. در جدول ۴ نتایج شیه سازی شده را برای راهکار پیشنهادی مشاهده می نمائید.

 

جدول 4

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

بنابراین برای ارزیابی این راهکار پیشنهادی ، توابع مود آزمایش به صورا دو بعدی و آنتی بادی ها به صورت اعداد حقیقی کد گذاری می شوند.

راهکار پیشنهادی با جستجوی محلی ژنتیک

در این قسمت جوادزاده و میبدی از الگوریتم ژنتیکی استاندارد جهت جستجوی محلی استفاده نموده اند و آنتی بادی های حافظه را با استفاده از آن بهبود می بخشند. برای مطالعه روند همگرایی راهکار پیشنهادی با جستجوی محلی ژنتیک ، بهترین ، بدترین میانگین و انحراف معیار ارزش صآنتی باتدی های حافظه برای تمام توابع ۱۰ تا ۱۳ گزارش شده اند.

جدول ۵ نتایج شبیه سازی راهکار پیشنهادی را نشان می دهد. نتایج نشان می دهند که راهکار پیشنهادی با جستجوی محلی ژنتیک به جواب های بهینه همگرا می شوند و برای مقایسه ، نتایج الگوریتم سیستم ایمنی مصنوعی استاندارد در جدول ۶ مشاهده می شود.

 

جدول 5 و 6

در راهکار پیشنهادی از الگوریتم ژنتیکی استاندارد با مشخصات ارائه شده در جدول ۷ به منظور بهبود در آنتی بادی های حافظه استفاده شده است. همچنین در این الگوریتم از مکانیزم انتخاب چرخ رولت به منظور انتخاب والدها در عملگر پیوند استفاده شده است.

 

جدول 7

با توجه به نتایج حاصله در جدول های ۵ و ۶ جوادزاده و میبدی نتیجه گیری کرده اند که کارایی راهکار پیشنهادی نسبت به الگوریتم سیستم ایمنی مصنوعی تائید شده است.

نتیجه گیری

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

 

برای دریافت مقاله به صورت pdf بر روی لینک کلیک کنید: Artificial-Immune-System-AIS

منبع


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

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

در سیستم ایمنی طبیعی، آنتی ژن ها موادی هستند که می توانند پاسخ ایمنی را ایجاد کنند. پاسخ ایمنی واکنش بدن به آنتی ژن است، بنابراین از صدمه زدن آنتی ژن به بدن جلوگیری می کند. آنتی ژن ها می توانند باکتری، قارچ، انگل و یا ویروس باشند. یک آنتی ژن باید به عنوان یک خارجی تشخیص داده شود.

وظیفه تشخیص آنتی ژن ها بر عهده گلبول سفید با نام لنفوسیت است. دو نوع لنفوسیت وجود دارد: T-Cell و B-Cell، که هر دو در مغز استخوان تولید می شوند. B-Cell ها در تماس با آنتی ژن ها، آنتی بادی هایی تولید می کند که در مقابل آنتی ژن ها موثر است. آنتی بادی ها پروتئین های شیمیایی هستند و دارای شکل Y مانند هستند.

آنتی بادی ها دارای گیرنده های خاص برای تشخیص آنتی ژن ها هستند. زمانی که تماس بین آنتی بادی با یک B-Cell و آنتی ژن برقرار می شود، تکثیر کلونی در سطح B-Cell اتفاق می افتد و به کمک T-Cell تقویت می شود. در صورت آنکه یک آنتی بادی به جای تشخیص آنتی ژن، بافت خودی را به عنوان عامل خارجی تشخیص داد خودش را نابود می کند.

در حین تکثیر کلونی، دو نوع از سلول شکل می گیرد: سلول های پلاسما و سلول های حافظه. وظیفه سلول های حافظه تکثیر سلول های پلاسما برای واکنش سریعتر در مواجه تکراری با آنتی ژن ها و تولید آنتی بادی برای آن هاست. سلول پلاسما یک سلول B-Cell است که آنتی بادی تولید می کند.

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

از عملکرد سیستم ایمنی بدن در تشخیص و انهدام عوامل خارجی برای طراحی الگوریتم های متنوعی در بهینه سازی، یادگیری ماشین و شناسایی الگو بهره برداری شده است. سیستم ایمنی مصنوعی یا AIS مخفف Artificial Immune System است که اولین بار به عنوان یک الگوریتم توسط دی کاسترو و زوبن تحت نام الگوریتم کلونی ارائه شد.

ایده اصلی در سیستم ایمنی مصنوعی، برگرفته از فرآیند تکثیر سلولی پس از تشخیص عامل خارجی در سیستم ایمنی طبیعی است. این فرآیند در سیستم ایمنی مصنوعی با نام انتخاب کلونی شناخته می شود و شامل سه مرحله است. در مرحله اول، گروهی از بهترین سلول ها ( سلول هایی که آنتی بادی مربوط به آنها بیشترین تطابق را با آنتی ژن ها داشته باشد) انتخاب می شود. در اینجا عملا هر سلول معادل یه پاسخ مساله است همانند کروموزوم در یک الگوریتم ژنتیک. در مرحله دوم، سلول های انتخاب شده تحت عملیات کلون قرار گرفته و با توجه به یک پارامتر با نام نرخ تکثیر، مورد تکثیر واقع می شود. تعداد کپی هایی که از هر سلول تولید می شود بستگی به ارزش آن سلول دارد. هر چقدر برازش یک سلول بیشتر باشد، تعداد کپی های بیشتری از آن ایجاد خواهد شد. در مرحله سوم، سلول تکثیر شده تحت عملگری با نام فراجهش قرار می گیرد. این عملگر که مشابه عملگر جهش در الگوریتم ژنتیک است، با توجه به پارامتری با نام Pm که نرخ جهش است، تغییر کوچکی را به هر سلول تکثیر شده اعمال می کند. (شبیه عملگر جهش در GA). تفاوتی که عملگر فراجهش با عملگر جهش در GA دارد آن است که در فراجهش، اندازه تغییراتی که در سلول ایجاد می شود بستگی به برازش آن سلول دارد. هر چقدر یک سلول برازنده تر باشد، تغییرات کمتری به آن اعمال خواهد شد.

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

خصوصیات مهم سیستم ایمنی مصنوعی به شرح زیر است:

1- استفاده از نمایش رشته بیتی

2- طول ثابت و یکسان برای هر سلول

3- به کارگیری یک جمعیت یا تعداد اعضا ثابت، البته در سیستم ایمنی مصنوعی می توان با تعریف طول عمر برای سلول های جمعیت، از یک جمعیت با تعداد اعضای متغیر نیز بهره برد.

4- در شبه کد، Selectionsize نشان گر تعداد سلول هایی است که برای انجام عملیات تکثیر، از جمعیت دور جاری در حلقه while انتخاب می شوند. به خاطر وجود همین مرحله در سیستم ایمنی مصنوعی، ماهیتی مشابه انتخاب داروینی وجود دارد.

5- برای تعیین عدد تکثیر سلولی برای یک سلول ایمنی انتخاب شده در تابع Clone از رابطه (Nc=Round(β,N,R استفاده می شود. در این رابطه Nc بیانگر تعداد کپی سلول β مبین نرخ تکثیرClonerate، همچنین N نشان گر تعداد سلول های جمعیت (Populationsize) و R بیانگر برازش مبتنی بر رتبه سلول مورد تکثیر است.

6- استفاده از جهش معکوش سازی بیت در عملگر فراجهش (عملگر جهش در AIS عملگر اصلی است).

7- برخلاف الگوریتم های تکاملی که معمولا احتمال جهش مقداری ثابت است، احتمال فراجهش Phm در سیستم ایمنی مصنوعی مقداری متغیر داشته و اندازه آن بستگی به برازش سلول ایمنی (عضو جمعیت) دارد. برای محاسبه احتمال فراجهش داریم: (Phm=exp(-Pm.f، در این رابطه Pm نرخ جهش بوده و f برازش سلول ایمنی مورد جهش است.

 

Code

 

منبع

 

 

سیستم ایمنی مصنوعی (AIS) قسمت 1
سیستم ایمنی مصنوعی (AIS) قسمت 2
سیستم ایمنی مصنوعی (AIS) قسمت 3
سیستم ایمنی مصنوعی (AIS) قسمت 4
سیستم ایمنی مصنوعی (AIS) قسمت 5
سیستم ایمنی مصنوعی (AIS) قسمت 6

نحوه عملکرد الگوریتم های ایمنی مصنوعی

الگوریتم های مطرح شده در سیستم های ایمنی مصنوعی را می توان به سه دسته تقسیم بندی نمود. دسته اول الگوریتم هایی که بر مبنای انتخاب جامعه سلول های B ایجاد شده اند. دسته دوم الگوریتم هایی که بر مبنای انتخاب معکوس سلول های T ایجاد شده اند. دسته سوم الگوریتم هایی که بر مبنای تئوری شبکه ایمنی بوجود آمده اند.

الگوریتم انتخاب جامعه (Clonal Selection)

این الگوریتم بر مبنای انتخاب جامعه سلول های B ایجاد شده است.بخش های اصلی این الگوریتم شامل شناسایی آنتی ژن، تکثیر و جهش سلول های B (آنتی بادی ها) و ایجاد سلول های حافظه است. در این الگوریتم اکثر سلول ها برای تکثیر انتخاب می شوند اما از همه سلول ها به یک اندازه تکثیر نمی شوند؛ بلکه سلول هایی که میل ترکیبی بیشتری دارند ، بیشتر تکثیر می شوند.

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

مراحل الگوریتم انتخاب جامعه

مراحل الگوریتم انتخاب جامعه عبارتند از :

 

 

Code Clonal Selection

 

مراحل الگوریتم انتخاب جامعه

 

الگوریتم انتخاب معکوس (Negative Selection)

این الگوریتم بر مبنای سلول های T ایجاد شده است.سلول های T می توانند سلول های خودی و غیر خودی را از یکدیگر تشخیص دهند.الگوریتم انتخاب معکوس دو مرحله دارد. مرحله اول که مرحله یادگیری است مشابه کار تیموس را انجام می دهد. یعنی سلول هایی که سلول های خودی را شناسایی می کنند را حذف می کند. مرحله دوم، مرحله نظارت یا اجراء است. در این مرحله الگوها (آنتی ژن ها) با سلول های T باقیمانده از مرحله اول مقایسه شده و در صورت شناسایی حذف می شوند. این الگوریتم در شناسایی الگو و امنیت نظارتی کاربرد دارد.

مراحل الگوریتم انتخاب معکوس

فرض می کنیم S مجموعه الگوهای خودی باشد که باید محافظت شده و مجموعه A نیز محافظ ها می باشند.

 

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

الگوریتم شبکه ایمنی (Immune Network)

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

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

S = Nt – ct + Ag

Nt : میزان تحریک شدن آنتی بادی توسط شبکه است.
ct : میزان بازدارندگی شبکه ای آنتی بادی می باشد.
A : میزان تحریک آنتی بادی توسط آنتی ژن است.

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

مراحل الگوریتم شبکه ایمنی مصنوعی

الگوریتم شبکه ایمنی مصنوعی را می توان بطور کلی به صورت زیر تعریف کرد:

Code Immune Network

مراحل الگوریتم شبکه ایمنی مصنوعی

الگوریتم aiNET

الگوریتم های متفاوتی برای شبکه ایمنی مصنوعی مطرح شده است که هر یک از آنها بخش های مختلف را به روش خود تعریف کرده اند. یکی از الگوریتم های معروف؛ الگوریتم aiNET می باشد. طبق تعریف aiNET گرافی وزن دار است که ممکن است کاملا همبند نباشد. گره های این گراف را آنتی بادی ها تشکیل می دهند و وزن لبه ها نمایانگر استحکام ارتباط میان دو گره می باشد. مراحل الگوریتم aiNET عبارتند از :

مراحل الگوریتم aiNETمراحل الگوریتم aiNET

مراحل ۱،۲ تا ۸،۲ در الگوریتم فوق انتخاب جامعه می باشد. در مرحله ۴،۲ جهش از رابطه   فرمول جهش   بدست می آید که در آن c’ ماتریس آنتی ژن، c جامعه آنتی بادی ها و ضریب یادگیری یا نرخ جهش است. نرخ جهش در این الگوریتم از حاصل ضرب یک عدد ثابت و یک عدد تصادفی با توزیع یکنواخت در بازه صفرو یک در فاصله آنتی بادی و آنتی ژن بدست می آید.

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

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

مراحل ۹،۲ و ۴ به ترتیب اعمال بازدارندگی جامعه و شبکه را انجام خواهند داد. در مرحله ۹،۲ الگوریتم عمل بازدارندگی روی مجموعه اعضاء جامعه ایجاد شده برای هر آنتی زن جاری انجام می گیرد و در مرحله ۴ این عمل بر روی تمامی آنتی بادی های شبکه انجام می شود. این دو مرحله باعث می شوند آنتی بادی هایی که آنتی ژن های مشابهی را شناسایی می کنند، حذف شوند.

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

پس از مرحله ۵ الگوریتم، خروجی شبکه به صورت مجموعه ای از آنتی بادی ها (گره های گراف) و میل ترکیبی آنها (لبه های گراف) بدست می آید که یک گراف کامل است. به منظور انجام عمل خوشه بندی، باید تعدادی از یال های گراف حذف شوند تا گراف خوشه های مختلف گراف از یکدیگر جدا شوند. برای این منظور می توان از مقدار آستانه استفاده کرد اما این روش کارایی ندارد.

در سال ۲۰۰۰ میلادی کاسترو در همایش شبکه های عصبی مصنوعی در ریودژانیروی برزیل، روش دیگری ارائه نمود. در روش کاسترو ابتدا درخت پوشای مینیمم گراف محاسبه شده و سپس یال هایی که مقدار آنها از یال های هم جوارشان به صورت مشخصی بیشتر است حذف می شوند. گره های باقیمانده به یک کلاس تعلق دارند.

 

Code aiNET Algorithm

 

معرفی انواع کاربرد سیستم های ایمنی مصنوعی

به طور کلی، سیستم‌های ایمنی مصنوعی جزء الگوریتم‌های الهام گرفته شده از بیولوژی هستند. این نوع الگوریتم‌ها، الگوریتم‍ هایی کامپیوتری هستند که اصول و ویژگی‌های آنها نتیجه بررسی در خواص وفقی و مقاومت نمونه‌ها بیولوژیکی است. سیستم ایمنی مصنوعی نوعی الگو برای یادگیری ماشین است. یادگیری ماشین، توانایی کامپیوتر برای انجام یک کار با یادگیری داده‌ها یا از روی تجربه است. تعریف کاسترو از سیستم ایمنی عبارتست از :

“سيستم هاي وفقي كه با الهام از ايمونولوژي نظري و توابع، اصول و مدل هاي ايمني مشاهده شده به وجود آمده‌اند و برای حل مسائل مورد استفاده قرار می‌گیرند.”

كاسترو و تيميس سه ویژگی زیر را برای الگوريتم ايمني مصنوعي معرفی نموده اند:

۱٫ در هر الگوريتم ايمني مصنوعي، حداقل بايد يك جزء ايمني مانند لنفوسيت ها وجود داشته باشد.
۲٫ در هر الگوريتم ايمني مصنوعي بايد ايده اي برگرفته از بيولوژي نظري يا تجربي استفاده شود.
۳٫ الگوريتم ايمني مصنوعي طراحي شده بايد به حل مسئله اي كمك كند.

بر اساس سه ویژگی فوق، كاسترو و تيميس، اولين الگوريتم هاي ايمني مصنوعي را در سال ۱۹۸۶ طراحي كردند. در همان سال فارمر مدلی برای تئوری شبکه ایمنی ارائه کرد و بر اساس این مدل اعلام کرد که “سیستم ایمنی قادر به یادگیری، به خاطر سپردن و تشخیص الگوست.” بعد از نظر فارمر، توجه به سیستم ایمنی مصنوعی به عنوان یک مکانیزم یادگیری ماشین شروع شد. پس از آن به تدریج سیستم ایمنی مصنوعی ، در زمینه‌های مختلف وفق پذیر و جذاب بودن خود را نشان داد.

سیستم ایمنی علاوه بر توانایی تشخیص الگو، صفات دیگری از قبیل یادگیری، حافظه، خود سازماندهی و از منظر مهندسی، خصوصیات دیگری مانند تشخیص بی‌قاعدگی، تحمل خطا، توزیع‌پذیری و مقاومت بالا دارا می باشد. از زمان آغاز بحث سیستم ایمنی مصنوعی ، این سیستم برای اهداف متنوعی به کار گرفته شده است. این کاربردها را می توان تحت ۹ عنوان کاربردی دسته‌بندی نمود. این عناوین کاربردی عبارتند از :

۱٫ تشخیص عیب (Fault Detection)
۲٫ تشخیص ناهنجاری (Anomaly Detection)
۳٫ تشخیص نفوذ (Intrusion Detection)
۴٫ امنیت اطلاعات (Information Security)
۵٫ مسائل بهینه سازی (Optimization Problems)
۶٫ دسته بندی الگوها (Patterns Classification)
۷٫ زمانبندی (Scheduling)
۸٫ خوشه بندی (Clustering)
۹٫ سیستم های یادگیرنده (Learning Systems)

در ادامه به تشریح دو مثال از کاربردهای سیستم ایمنی مصنوعی می پردازیم.

سیستم ایمنی مصنوعی (AIS) قسمت 1
سیستم ایمنی مصنوعی (AIS) قسمت 2
سیستم ایمنی مصنوعی (AIS) قسمت 3
سیستم ایمنی مصنوعی (AIS) قسمت 4
سیستم ایمنی مصنوعی (AIS) قسمت 5
سیستم ایمنی مصنوعی (AIS) قسمت 6

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

ابتدا یک کروموزوم رندوم انتخاب می شود (کروموزومی به غیر از بهترین کروموزومی که در صدر لیست قرار دارد). سپس دو ژن رندوم از این کروموزوم انتخاب می شود و با هم جابجا می شود. افزایش تعداد میوتیشن ها آزادی الگوریتم را در جستجو خارج از فضای حالات کروموزوم ها بیشتر می کند.

همان طور که گفته شد ژن عددی از ۰ تا ۷ است که به معنی شماره سطری است که وزیر در آن قرار گرفته است. موقعیت ژن در یک کروموزوم به معنی شماره ستون قرار گیری وزیر است. مشخص کردن مکان قرار گیری هر وزیر را باید حتما در هر سطر و ستون مشخص کرد.

کروموزوم نیز مجموعه ای از ۸ ژن است. و این طور فرض می شود که هیچ ژنی در یک کروموزوم دوبار تکرار نشود. برای مثال اگر کروموزوم ما ۰|۱|۴|۲|۳|۶|۷|۵ باشد یعنی ۸ وزیر در خانه های زیر از ماتریس قرار گرفته اند.

(۰,۰), (۱,۱), (۲,۴), (۳,۲), (۴,۳), (۵,۶), (۶,۷), (۷,۵)

در اینجا میوتیشن با swap کردن ژنی که باید mutate شود با یک ژن تصادفی (به جز ژنی که می خواهیم میوتیشن را روی آن انجام دهیم) از همان کروموزوم انجام می شود.

در crossover ژن ها از کروموزوم های دو والدین با احتمال ۰٫۵ گرفته می شود. یک ژن از یکی از والدین گرفت می شود و به کروموزوم فرزند اضافه می شود. ژنی که تولید می شود در پرنت دیگر پاک می شود. این مرحله انقدر ادامه می یابد تا کروموزوم های پدر و مادر هر دو، خالی شود و فرزند آنها همه ژن ها را داشته باشد.

تابع فیتنس: زمانی که دو وزیر طوری قرار بگیرند که یکدیگر را تهدید کنند یعنی در یک سطر، ستون یا قطر مشابه باشند. از آنجایی که کروموزوم ها ژن های تکراری ندارند بنابراین این اطمینان وجود دارد که هیچ دو وزیری در یک ستون قرار نمی گیرند. پس تنها باید برخوردهای قطری را بررسی و محاسبه کرد. بنابراین ماکزیمم تعداد برخوردها می تواند ۲۸ باشد. تابع فیتنس مقدارش هر چه بیشتر باشد بهتر است بنابراین اگر یک راه حل ۰ برخورد (تهدید دو وزیر) داشته باشد فیتنس آن ۲۸ است که با تفریق مقدار برخوردهایی که در حالت فعلی رخ می دهند از ۲۸ به دست می آید.

در کد c# مورد استفاده :

class GeneticAlgo: کلاسی است که مسئولیت همه عملیات الگوریتم ژنتیک را بر عهده دارد.

class FitnessComparator: یک کلاس مقایسه کننده است که کروموزوم ها را با fitness value مرتب می کند تا جمعیت نهایی را در جدول نشان دهد. بیشترین فیتنس در بالای جدول قرار می گیرد و کمترین آنها در پایین جدول.

struct Chromosome: ساختاری است که کروموزومی که حاوی ژنهااست، فیتنس و مجموع میانگین فیتنس ها را نشان می دهد.

class MainFrame: این کلاس موظف به کنترل اینترفیس کاربر و ایجاد جمعیت اولیه به منظور انتقال آن به الگوریتم ژنتیک است.

class Board: این کلاس گرافیک و عملیات صفحه شطرنج را بر عهده دارد.

متغیر private const int MAX_FIT = ۲۸ بیشترین مقدار فیتنس را دارد.

توابع:


private List<chromosome> GetInitialPopulation(int population)

{

List<chromosome> initPop = new List<chromosome>();

GeneticAlgo RandomGen = new GeneticAlgo();

for (int i = 0; i < population; i++)

{

List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});

Chromosome chromosome = new Chromosome();

chromosome.genes = new int[8];

for (int j = 0; j < 8; j++)

{

int geneIndex = (int)(RandomGen.GetRandomVal

(۰,genes.Count-1)+0.5);//randomly select a gene

chromosome.genes[j] = genes[geneIndex];

genes.RemoveAt(geneIndex);//remove selected gene

}

initPop.Add(chromosome);

}

return initPop;

}

 

تابع فوق اندازه جمعیت را به صورت پارامتر می گیرد و لیستی از کروموزوم هایی که دربردارنده ژن های تولید شده تصادفی هستند را بر می گرداند. مقدار ژن ها بصورت تصادفی از لیستی که شامل اعداد ۰ تا ۷ است انتخاب می شود. در حین اینکه مقادیر از لیست انتخاب می شوند، مقادیر انتخاب شده پاک می شوند تا از تکراری شدن ژن ها در کروموزوم جلوگیری شود. اندازه لیست مساوی با اندازه جمعیت است. پس از ایجاد جمعیت اولیه با استفاده از این تابع، لیست کروموزوم هایی که برمیگرداند به تابع DoMating داده می شود.


public void DoMating(ref List<Chromosome> initPopulation,

int generations, double probCrossver, double probMutation)

{

int totalFitness = 0;

CalcFitness(ref initPopulation, ref totalFitness);

for (int generation = 0; generation < generations; generation++)

{

PrepareRuletteWheel(ref initPopulation,totalFitness);

Crossover(ref initPopulation, probCrossver);

Mutate(ref initPopulation, probMutation);

CalcFitness(ref initPopulation, ref totalFitness);

if (initPopulation[initPopulation.Count – 1].fitness == 28)

break;

if (progress != null)

{

progress(generation + 1);

}

}

initPopulation.Sort(new FitnessComparator());

}
 

این تابع لیست کروموزوم ها را به عنوان جمعیت اولیه ، تعداد نسل هایی که می خواهیم در الگوریتم پخش شوند، احتمال crossover و احتمال mutation را به عنوان پارامتر می گیرد. مسئولیت این تابع هندل کردن پخش جمعیت به نسل مورد نیاز با فراخوانی توابع CalcFitness،PrepareRuletteWheel،CrossoverوMutate است.

 

public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)

{

int collisions = 0;

totalFitness = 0;

for (int k = 0; k < chromosome.Count; k++)

{

for (int i = 0; i < chromosome[k].genes.Length – 1; i++)

{

int x = i;

int y = chromosome[k].genes[i];

for (int j = i + 1; j < chromosome[k].genes.Length; j++)

{

if (Math.Abs(j – x) == Math.Abs

(chromosome[k].genes[j] – y))

collisions++;

}

}

Chromosome temp = chromosome[k];

temp.fitness = MAX_FIT – collisions;

chromosome[k] = temp;

totalFitness += chromosome[k].fitness;

collisions = 0;

}

}

این تابع فیتنس هر کروموزوم را اندازه می گیرد و fitness value را به مشخصه fitness  هر کروموزوم تخصیص می دهد. فیتنس با محاسبه تعداد برخوردها و کم کردن آن از ماکزیمم تعداد برخورد ها محاسبه می کند. در این کد فیتنس تابعی است که هرچه مقدارش بیشتر باشد بهتر است. علاوه بر محاسبه فیتنس هر کروموزوم، این تابع می تواند فیتنس کلی جمعیت را نیز محاسبه کند زیرا در مرحله بعدی برای محسابه نرخ فیتنس هر کروموزوم به آن نیاز داریم.


private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)

{

int currentTotalFitness=0;

for (int i = 0; i < parents.Count; i++)

{

currentTotalFitness += parents[i].fitness;

Chromosome temp = parents[i];

temp.cumAvgFitness = currentTotalFitness / (double)total;

parents[i] = temp;

}

}

rulette wheel که بر مبنای فیتنس کروموزوم است برای انتخاب والدین برای جفت گیری برای ایجاد نسل جدید استفاده می شود. این تابع مسئول آماده سازی rulette wheel بوده و لیستی از کروموزوم ها را به عنوان جمعیت فعلی و فیتنس کلی جمعیت می گیرد. این تابع نرخ فیتنس هر کروموزوم تا فیتنس کلی را محاسبه می کند سپس مجموع آن را برای اختصاص به مشخصه cumAvgFitness  کروموزوم محاسبه می کند.

با تابع RuletteWheel می توان احتمال انتخاب را بر اساس نرخ فیتنس تعیین کرد. با این روش کروموزم هایی با fitness value بالاتر احتمال بیشتری برای انتخاب در ساخت نسل بعدی دارند در حالی که کروموزم هایی با fitness value پایین تر با احتمال کمتری شرکت داده می شوند


public void Crossover(ref List<Chromosome> parents, double probability)

{

List<Chromosome> offspring = new List<Chromosome>();

for (int i = 0; i < parents.Count; i++)

{

if (Assay(probability)) //if the chance is to crossover

{

Chromosome parentX = AssayRuletteWheel(parents);

Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();

for (int j = 0; j < 8; j++)

{

if (Assay(0.5)) //select from parentX

{

for (int k = 0; k < parentX.genes.Length; k++)

{

if (!child.Contains

(parentX.genes[k]))//instead of

//deleting the similar genes

//from parents select the

//next non-contained number

{

child.Add(parentX.genes[k]);

break;

}

}

}

else //select from parentY

{

for (int k = 0; k < parentY.genes.Length; k++)

{

if (!child.Contains

(parentY.genes[k]))//instead of

//deleting the similar genes from

//parents select the next

//non-contained number

{

child.Add(parentY.genes[k]);

break;

}

}

}

}

Chromosome offSpr = new Chromosome();

offSpr.genes = child.ToArray();

offspring.Add(offSpr);

}

else //else the chance is to clone

{

Chromosome parentX = AssayRuletteWheel(parents);

offspring.Add(parentX);

}

}

while (offspring.Count > parents.Count)

{

offspring.RemoveAt((int)GetRandomVal(0, offspring.Count – 1));

}

parents = offspring;

}

 

تابع فوق مسئول انجام عمل cross over است. تابع لیستی از کروموزم ها را به عنوان جمعیت فعلی و احتمال crossover را به عنوان پارامتر می گیرد. تابع Assay(int probability) با احتمال داده شده true بر می گرداند بنابراین با احتمال crossover برای تعیین اینکه عملیات crossover است یا cloning استفاده می شود.

if (Assay(probability)) //if the chance is to crossover

{

Chromosome parentX = AssayRuletteWheel(parents);

Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();

for (int j = 0; j < 8; j++)

{

if (Assay(0.5)) //select from parentX

{

for (int k = 0; k < parentX.genes.Length; k++)

{

if (!child.Contains(parentX.genes[k]))//instead of

//deleting the similar genes from parents

//select the next non-contained number

{

child.Add(parentX.genes[k]);

break;

}

}

}

else //select from parentY

{

for (int k = 0; k < parentY.genes.Length; k++)

{

if (!child.Contains(parentY.genes[k]))//instead of

//deleting the similar genes from parents

//select the next non-contained number

{

child.Add(parentY.genes[k]);

break;

}

}

}

}

Chromosome offSpr = new Chromosome();

offSpr.genes = child.ToArray();

offspring.Add(offSpr);

}

این بخش از کد مسئول crossover دو پرنت parentX  و parentY می باشد. به منظور ایجاد فرزند، ژنها از دو والدین با احتمال ۰٫۵ انتخاب می شوند در حالیکه از تکرار ژنها در کروموزوم ها اجتناب می شود. در عملیات cloning یکی از والدین مستقیما به نسل بعدی آورده می شود.


public void Mutate(ref List&amp;lt;Chromosome&amp;gt; parents, double probability)

{

List&amp;lt;Chromosome&amp;gt; offsprings = new List&amp;lt;Chromosome&amp;gt;();

for (int i = 0; i &amp;lt; parents.Count; i++)

{

Chromosome offspring = parents[i];

for (int mutatePosition = 0; mutatePosition &amp;lt; 8; mutatePosition++)

{

if (Assay(probability)) //if the chance is to mutate

{

int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);

if (newGeneIndex&amp;gt;=mutatePosition)

{

newGeneIndex += 1;

}

int swapTemp = offspring.genes[mutatePosition];

offspring.genes[mutatePosition] =

offspring.genes[newGeneIndex];

offspring.genes[newGeneIndex] = swapTemp;

}

}

offsprings.Add(offspring);

}

parents = offsprings;

}
 

این تابع اپراتور mutation را با احتمال داده شده استفاده می کند. این تابع تغییر میوتیش را در حین انتقال ژن ها در جمعیت فعلی بررسی می کند. اگر باید برای ژنی از میوتیشن استفاده شود آنگاه مقدار آن با یک ژنی که بصورت تصادفی انتخاب شده در همین کروموزوم (ژنی به جز خود ژنی که می خواهیم روی آن میوتیشن انجام دهیم)  swap می شود.

زمانی که به یک راه حل می رسیم آرایه ژن های کروموزومی که شامل راه حل هستند را میتوان به پراپرتی به نام Genes  در کلاس Board اختصاص داد.

این برنامه این امکان را می دهد که اندازه جمعیت، تعداد نسل ها، احتمال crossover و احتمال mutation را مشخص کنید.

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

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

این سوال ها سالها مطرح بوده است که بین crossover و mutation کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟ پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده این است که هر کدام نقش مخصوص خود را دارد. در حالت کلی بهتر است از هر دو استفاده شود. میتوان الگوریتمی داشت که فقط از mutation استفاده کند ولی الگوریتمی که فقط ازcrossover   استفاده کند کار نخواهد کرد. Crossover خاصیت جستجوگرانه و یا explorative دارد. میتواند با انجام پرشهای بزرگ به محل هائی دربین والدین رفته و نواحی جدیدی را کشف نماید. Mutation خاصیت گسترشی و یا  exploitive  دارد. میتواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد.  Crossoverاطلاعات والدین را ترکیب میکند درحالیکه mutation  میتواند اطلاعات جدیدی اضافه نماید. رسیدن به یک پاسخ بهینه در mutation شانسی است.

نتایج اجرای این الگوریتم نشان می دهد که جمعیت عامل بسیاری مهمی بوده و تاثیر زیادی دارد و crossover probability و mutation rate تاثیر غیر قابل انکاری بر اجرای الگوریتم ژنتیک دارند زیرا با هر بار تغییر در هر یک از این پارامترها نتایج به شدت تغییر می کند. در حقیقت نحوه انتخاب اپراتورهای GA یک تریدآف بین همگرایی سریع تر و حفظ قابلیت اکتشافی بودن الگوریتم (برای جلوگیری از همگرایی اشتباه) است. Crossover پارامتری است که به تنظیم رفتار الگوریتم ژنتیک کمک می کند. کم کردن احتمال crossover باعث می شود در نسل بعدی افراد بیشتری بدون تغییر باقی بمانند. بسته به مسئله کاهش یا افزایش مقدار احتمال crossover می تواند تاثیر مثبت یا منفی داشته باشد.

پس از اجراهای متوالی الگوریتم می توان دید که هیچ جوابی وجود ندارد گه به طور قطع بتوان گفت از بقیه بهتر است و بتوان گفت که مقدار تنظیم شده برای پارامترهای الگوریتم ژنتیک در این حالت از همه بهتر است. این بهترین مقادیر به عوامل زیادی وابسته هستند. برای مثال اگر الگوریتم شما generational است میخواهید احتمالی را برای این در نظر بگیرید که برخی از والدین بدون تغییر باقی بمانند. در غیر اینصورت برخی راه حل های خوب را از دست خواهید داد. بنابراین بهتر است crossover rate را نزدیک به ۰٫۷ تنظیم کرد. برخی از الگوریتم ها نیز هستند که به طور کامل به mutation وابسته اند و برای آنها crossover rate مساوی با ۰ در نظر گرفته می شود. اگر crossover probability برابر با ۱۰۰درصد باشد همه فرزندان توسط crossover ایجاد می شوند. اگر ۰ درصد باشد همه نسل جدید کپی دقیقی از کروموزوم فعلی جمعیت قدیمی است ولی به این معنی نیست که نسل جدید دقیقا همان نسل قبلی است.

انتخاب اپراتورهای الگوریتم توازنی میان سرعت و دقت همگرایی است یعنی exploration در مقابل exploitation.

اینطور که گفته شده بهتر است mutation بین ۰٫۰۱۵ تا ۰٫۰۲ باشد. چرا؟

Exploration یعنی جستجوی فضای حالت در حد امکان در حالی که exploitation یعنی تمرکز بر یک نقطه که امیدواریم global optimum باشد.

در GA اپراتورهای mutation اغلب برای exploration و اپراتور های Crossover اغلب برای exploitation یعنی هدایت جمعیت به سوی همگرایی به یک راه حل خوب استفاده می شوند. در نتیجه وقتی Crossover سعی در همگرایی به یک نقطه مشخص دارد mutation سعی خود را می کند که همگرایی صورت نگیرد و فضای بیشتری کاوش شود.

در ابتدای فرایند جستجو ترجیح ما بر این است که جستجوی بیشتری به منظور اکتشاف فضا صورت گیرد. از طرف دیگر در انتهای فرایند جستجو exploitations بیشتری ترجیح داده می شود که همگرایی جمعیت به سمت global optimum تضمین شود. تنها یک استثناء وجود دارد؛ زمانی که جمعیت به سمت بهینه محلی همگرا می شود اگر بتوانیم باید پراکندگی حمیت را افزایش دهیم تا فضای بیشتری جستجو شود و در دام بهینه محلی نیفتد. با توجه به این نکته mutation rate بالا باعث افزایش احتمال جستجوی فضای بیشتری از فضای جستجو می شود با این حال از همگرایی جمعیت به یک جواب بهینه جلوگیری می کند. از طرف دیگر اگر mutation rate خیلی کوچک باشد باعث همگرایی زودهنگام و نارس می شود و به حای رسیدن به global optimum در دام بهینه محلی گرفتار می شود.مقداری که انتخاب می شود به ماهیت مسئله و نحوه پیاده سازی الگوریتم بستگی دارد. پس mutation rate های بسیار بالا از همگرایی الگوریتم جلوگیری کرده و رسیدن به راه حل بهینه را تضمین نمی کنند. بنابراین عاقلانه تر این است که از mutation rate های کوچک تر استفاده شود. مقدار کوچک برای mutation rate تضمین می کند که میوتیشن های زیادی در آن واحد اتفاق نیفتد ولی این نیز به تعداد ژن های موجود در هر کروموزوم از جمعیت بستگی دارد. بهتر این است که با مقادیر کم شروع کرده و به تدریج آنها را افزایش داد و کارایی هر یک را بررسی کرد مثلا به ترتیب: ۰٫۰۰۱، ۰٫۰۱، ۰٫۰۵، ۰٫۱، ۰٫۲ و … . در رابطه با جستجو در فضای حالت در مقایسه با mutation rate بالاتر، جمعیت بزرگتر ترجیح داده می شود.

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

Exploitation = (crossover +  انتخاب بر اساس فیتنس) ما را به جواب بهینه نهایی می رساند.

این طور گفته می شود که اندازه جمعیت کوچکتر سرعت همگرایی بیشتری به الگوریتم می دهد ولی الگوریتم راحتتر در بهینه محلی گرفتار می شود. احتیاط بر این است که از جمعیت های بیش از حد کوچک استفاده نشود. معمولا به احتمال crossover و mutation بسیار بزرگ نیاز نخواهید داشت و جمعیتی با اندازه متوسط مناسب است.

است.
مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4