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

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

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

ترکیب و تشخیص کامپیوتری صحبت مسائل دشواری هستند. روشهای مختلفی مورد آزمایش قرار گرفت هاند که موفقیت کمی داشته‌اند. این زمینه از زمینه‌های فعال در تحقیقات پردازش سیگنال دیجیتال (دی. اس. پی) بوده و بدون شک سالها این گونه خواهد ماند. در حال حاضر از ابزارهای برنامه‌نویسی جاافتاده در زمینه‌های برشمرده شده می‌توان به‌ای. پی. آی صحبت شرکت مایکروسافت اشاره نمود که دارای تواناییهای عمدهای در زمینه‌های تشخیص و ترکیب صحبت است و توانایی آن تا حدی گسترده‌است که در محصول بزرگ واز آن استفادهٔ عملی شده‌است. ابزار عمد هی دیگر تولید شرکت آی. بی. ام است و 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

پردازش گفتار

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

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

مقدمه

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

۱-تحت تاثیر قرار گرفتن کیفیت سیگنال صوتی به وسیلهٔ نویز محیط و تابع انتقال سیستم انتقال مانند میکروفن، تلفن

۲-عدم وضوح مرز ما بین کلمات و واج‌ها در سیگنال صوتی

۳-تنوع وسیع سرعت بیان

۴-دقت ناکافی در بیان کلمات و به خصوص انتهای انها در گفتار محاوره‌ای نسبت به گفتار مجزا.

۵-تاپیر تنوعات متعدد گوینده از جمله جنسیت، شرایط فیزیولوژیک و روانی بر گفتار.

۶-به کارگیری محدودیت‌های معنایی-نهوی زبان برای گفتار زبان طبیعی به روشی مشابه ارتباط انسان با انسان در سیستم بازشناسی.

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

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

تولید نرم‌افزار ترجمه گفتار

از جمله قابلیت‌های این نرم‌افزار این است که این نرم‌افزار قادر است فایلهای WAV،mp3 را مستقل از صدای گوینده به متن تبدیل کند ولی کیفیت ان کمتر از ان است که صدای فرد را به نرم‌افزار معرفی کنیم. از دیگر قابلیت‌های سیستم‌های گفتاری می‌توان به ترجمهٔ گفتار به سایر زبان‌ها اشاره کرد. از این قابلیت در جنگ امریکا و عراق استفاده شد. امریکایی‌ها سیستم‌هایی را طراحی و تولید کردند که قادر بود کلام عربی را به انگلیسی ترجمه کند. همچنین در انجام اقدامات امنیتی بهره برداری می‌کنند که می‌تواند کلمات کلیدی را برای این نرم‌افزار شناسایی کرد تا نسبت به ان کلمه خاص حساس شود تا در صورت استفاده از آن، سیستم این کلمات را رکورد کند. این قابلیت در سال ۱۹۹۴ در آمریکا طراحی و تولید شد و در سیستم‌های تلفنی به کار گرفته شد. در حال حاضر این نرم‌افزار طراحی و تولید شده‌است به گونه‌ای که در متن و گفتار کاربر، کلمهٔ خاصی را می‌توان فعال کرد و این نرم‌افزار می‌تواند ان کلمه را جستجو کند و کلمهٔ عبور کاربر ذخیره شود.

کاربردهای نرم‌افزار تشخیص گفتار (پردازش گفتار)

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

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

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

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

تکنولوژی بازشناسی گفتار

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

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

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

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

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

به عنوان نمونه از این نرم‌افزار در دادن فرامین صوتی به خودرو ویژه هنگامی که راننده مشغول رانندگی است و نمی‌تواند کاربری دیگری انجام دهد، استفاده می‌شود فرامین صوتی شامل موارد ذیل می‌شوند:

۱- تنظیم آینه‌های بغل و عقب

۲- کنترل بالابر شیشه‌ها

۳- کنترل قفل کودک

۴- کنترل روغن ترمز و موتور یا بنزین در حال حرکت

۵- کنترل رادیو یا هر نوع رسانه دیگر در خودرو

۶- کنترل برف پاک کن‌ها

۷- تنظیم صندلی‌ها

۸- کنترل چراغ‌ها

۹- هر نوع دستور دیگر که انجام آن نیازمند حرکت اضافی راننده یا سرنشینان است.

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

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

گزارش طرح نرم‌افزار فناوری بازشناسی گفتار (پردازش گفتار)

۱- عنوان طرح: فناوری بازشناسی گفتار مقاوم در برابر نویز ۲- توضیح عمومی و کاربرد: با استفاده از این فناوری، صدای ضبط شده توسط یک میکروفون بازشناسی شده و به فرامین برای یک دستگاه الکترونیکی یا رایانه، تبدیل می‌شوند حوزه کاربرد این فناوری تمامی دستگاه‌های الکتریکی، الکترونیکی و رایانه‌ای است که به طریقی از کاربر فرمان می‌گیرند. تمام فرامین قابل بیان با استفاده از مجموعه متناهی کلمات گسسته را می‌توان با استفاده از این فناوری توسط میکروفون به دستگاه یا رایانه داد.

۳- مزایا در مقایسه با دیگر فناوری‌های مشابه: مهمترین خصوصیات این فناوری نیاز به توان پردازشی بسیار کم و مقاومت بسیار زیاد در مقابل سرو صدای محیط (نویز) است.

۴- شرح طرح: روش ارائه شده از سه بخش اصلی تشکیل شده‌است

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

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

ج ـ بخش سوم که داده‌های گرفته شده از بخش اول را با الگوهایی که در بخش دوم یاد گرفته شده‌اند مقایسه می‌کرده و شبیه‌ترین کلمه را انتخاب می‌کند.

استخراج ویژگی‌ها از سیگنال صدا:

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

۱- استخراج اسپکتروگرام صدا

۲- اعمال فیلترهای فیوژن ماکسیمم –ان بر روی فریم‌های اسپکتروگرام تولید شده

۳- اعمال فیلترهای شناسایی یکنواختی در طول اسپکتروگرام

الف ـ اولین مرحله در بازشناسی صدا، تبدیل سیگنال صدای ورودی به اسپکتروگرام با طول محدود است برای این کار با استفاده از الگوریتم استاندارد تبدیل سریع فوریه تبدیلات فوریه پنجره‌هایی به طول ۵۱۲ صدای ضبط شده با ۱۲۸ فریم همپوشانی گرفته و در کنار یکدیگر قرار داده می‌شود در پایان این مرحله، سیگنال یک بعدی صدا به تصویری دوبعدی تبدیل می‌شود

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

بازشناسی الگوها

در این بخش الگوریتم مقایسه یک ورودی صوتی با الگوی کلماتی که از قبل یاد گرفته شده‌اند ارائه می‌شود برای این کار الگوریتم مقایسه کشسان (۱) ارائه می‌شود. برای تصمیم گیری نهایی ورودی این بخش با تمام کلماتی که قبلاً یاد گرفته شده‌اند توسط این الگوریتم مقایسه شده و کلمه‌ای که بیشترین تطابق را داشته باشد به عنوان جواب انتخاب می‌شود. الگوریتم مقایسه کشسان ساختاری مشابه ماشین حالات محدود (۲) دارد با ۳ تفاوت مهم زیر (از این به بعد این الگوریتم را ماشین تطبیق دهندهٔ قابل انعطاف یاEMM می‌نامیم.) 1- بر خلاف EMM، FSM ممکن است بیش از یک حالت فعال در هر زمان وجود داشته باشد تعداد حالات فعال در زمان‌های مختلف نیز متفاوت است. در صورتی که یک EMM به وضعیتی برسد که هیچ حالت فعالی نداشته باشد به پایان کار خود رسیده‌است. 2- در EMM حالات فعال به جز شماره حالت خصوصیات دیگری نیز دارند. فهرست این خصوصیات عبارتند از:

الف ـ میزان تطابق وضعیت (۳)‌های قبلی: این معیار مشخص می‌کند که اگر اکنون در وضعیت N ام ماشین باشیم. N-1 وضعیت قبلی با چه درجه تطابقی شناسایی شده‌است.

ب ـ میزان تطابق وضعیت قبلی: این معیار، بیانگر میزان تطابق درست بین ورودی‌هایی که به این وضعیت انتساب داده شده‌اند با الگوریتم خواسته شده برای این وضعیت است.

3- در EMM مشابه ماشین‌های حالت محدود غیرقطعی (۴) با یک ورودی و از یک وضعیت ممکن است توان حرکت به بیش از یک وضعیت دیگر وجود داشته باشد در چنین حالتی تمامی وضعیت‌های بعدی همزمان تولید و پیموده می‌شوند.

روش کار EMM به این شکل است که برای مقایسه یک کلمه (الگو) با یک ورودی Ii فریم‌های خروجی بخش پیش پردازش اطلاعات (۱-۴) برای ورودی و Pi فریم‌های خروجی بخش یادگیری برای الگو خوانده خواهند شد. برای این کار یک EMM ساخته می‌شود که به اندازه فریم‌های الگو وضعیت دارد و انتقال بین وضعیت‌ها فقط در طول محور فریم‌های الگو قابل انجام است به این ترتیب با خواندن هر فریم ورودی (Ii) یا باید در وضعیت سابق الگو بمانیم یا به وضعیتی بعد از آن منتقل شویم. به این ترتیب با رسیدن هر فریم ورودی هر وضعیت فعلی فعال EMM به دو وضعیت جدید تبدیل می‌شود اما باید به طریقی از این افزایش نمایی جلوگیری کرد برای این کار وضعیت‌هایی که درجه شناسایی درستشان از حد خاصی کمتر باشد حذف می‌شوند.

تلفن همراه SPH-P۲۰۷ ساخته شرکت سامسونگ دارای نرم‌افزاری تشخیص گفتار است. که براین اساس به پیام‌های گفتاری سریعتر از تایپ کردن آنها روی صفحه شماره گیری جواب می‌دهد وظیفه اصلی این تلفن بی سیم تبدیل گفتار انسان به سیگنال‌های دیجیتالی و بالعکس می‌باشد تلفن SPH-P۲۰۷ سامسونگ اولین تلفنی است که از فناوری تشخیص گفتار برای دیکته یک متن استفاده میشود.

 

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

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

الگوریتم‌های DSP مدت زیادی است که در کامپیوترهای استاندارد همه منظوره، یا بر روی پردازش‌گرهای معروف به پردازشگرهای سیگنال دیجیتال (DSP) یا با استفاده از سخت‌افزارهای خاص مثلمدارهای مجتمع با کاربرد خاص (ASIC) اجرا می‌شوند. امروزه تکنولوژی‌های دیگری نیز برای پردازش سیگنال دیجیتال مورد استفاده قرار می‌گیرند که شامل میکروپروسسورهای چندمنظوره قدرتمند،اف‌پی‌جی‌ای (FPGA)، کنترل‌کننده سیگنال دیجیتال (بیشتر برای کاربردهای صنعتی مثل کنترل موتور) هستند.

حوزه‌های DSP

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

نمونه‌برداری از سیگنال

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

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

در مرحله مدرج کردن، مقادیر سیگنال نماینده (به انگلیسی: Representative Signal) توسط مقادیر زیر مجموعه یک مجموعه متناهی تقریب زده می‌شوند.

قضیه نمونه‌برداری نایکوئیست-شنون بیان می‌کند که سیگنال را می‌توان از روی سیگنال نمونه‌برداری شده به طور دقیق بازسازی کرد، اگر فرکانس نمونه‌برداری بزرگتر از دو برابر بالاترین مؤلفه فرکانسی سیگنال باشد. در عمل، غالباً فرکانس نمونه‌برداری را بزرگتر از دو برابر پهنای باند لازم در نظر می‌گیرند.

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

مفهوم حوزه‌ی زمان و فرکانس

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

  • “فیلتر خطی”: یک تبدیل خطی است که بر روی نمونه های ورودی اعمال میشود؛ سایر فیلترها “غیرخطی” هستند. فیلترهای خطی از قاعده ی جمع آثار پیروی میکنند؛ به این معنی که اگر یک سیگنال ورودی، ترکیب وزنداری از سیگنال های مختلف باشد، سیگنال خروجی از ترکیب خطی خروجی های همان سیگنال ها، با وزنهای مشابه ورودی، حاصل میشود.
  • “فیلتر علی”: فیلتر علی فقط از نمونه های قبلی در سیگنال های ورودی و خروجی استفاده میکند. اما، در فیلترهای “غیرعلی”، نمونه های آینده ی ورودی نیز به کار گرفته می شوند. با اضافه کردن تأخیر به یک فیلتر غیرعلی میتوان آنرا به یک فیلتر علی تبدیل نمود.
  • “فیلتر غیر متغیر با زمان”: ویژگی های این فیلتر با زمان تغییر نمیکند. اما، فیلترهایی مانند فیلتر تطبیقی، با زمان تغییر میکنند.
  • “فیلتر پایدار”: خروجی یک فیلتر پایدار با گذشت زمان به یک مقدار ثابت همگرا میشود یا در محدوده ی متناهی باقی می ماند. اما، یک فیلتر “ناپایدار” در پاسخ به یک ورودی محدود (متناهی) یا حتی صفر، ممکن است منجر به تولید خروجی هایی نامتنهای شود.
  • “فیلتر با پاسخ ضربه ی محدود (FIR)”: این فیلتر فقط از نمونه های سیگنال ورودی استفاده میکند، اما، فیلتر با پاسخ ضربه ی نامحدود (IIR) علاوه بر نمونه های ورودی، از نمونه های گذشته ی خروجی نیز استفاده میکند. فیلترهای FIR همواره پایدار هستند، اما، فیلترهای IIR ممکن است ناپایدار شوند.

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

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

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

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

فیلترینگ سیگنال، به ویژه در کابردهای غیر زمان واقعی (non- real time)،میتواند با انتقال سیگنال به حوزه ی فرکانس و اعمال یک فیلتر مناسب بر آن و سپس برگرداندن سیگنال حاصل به حوزه ی زمان انجام شود. این عملیات، سریع بوده (زمان اجرا متناسب است با (n log n) ) و می توان فیلتر را با تقریب خوبی به شکلهای مختلف طراحی نمود.

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

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

بسط فوریه و مفهوم حوزه زمان (منحنی قرمز) و فرکانس (منحنی آبی).

تحلیل در حوزه {\displaystyle Z\,}

در حالی که فیلترهای آنالوگ معمولاً در صفحه{\displaystyle s\,} تحلیل می‌شوند، فیلترهای دیجیتال در صفحه {\displaystyle z\,} یا حوزه دیجیتال و با استفاده از تبدیل {\displaystyle Z\,} تحلیل می‌شوند.

بسیاری از فیلترها را می‌توان در حوزه{\displaystyle Z\,} (یک فرامجموعه از اعداد مختلط در حوزه فرکانس) توسط تابع تبدیلشان تحلیل کرد. یک فیلتر می‌تواند توسط مجموعه مشخصه‌اش شامل صفرها و قطب‌ها در حوزه{\displaystyle z\,} تحلیل شود.

کاربردها

بیشترین کاربردهای DSP شامل پردازش سیگنال صوتی، فشرده‌سازی داده‌های صوتی، پردازش تصویر دیجیتال، فشرده‌سازی ویدیو، پردازش صدا، تشخیص صدا، ارتباط دیجیتال، رادار، سونار، زلزله‌شناسی و داروسازی است. مثال‌های خاص شامل فشرده‌سازی صحبت و انتقال در تلفن همراه، هم‌نواسازی مطابق اتاق برای صدا در کاربردهای شباهت زیاد به اصل و تقویت صدا، پیش بینی وضع هوا، پیش‌بینی اقتصادی، پردازش داده زلزله، تحلیل و کنترل روال‌های صنعتی، انیمیشن‌های تولید شده توسط رایانه در فیلم‌ها، عکس‌برداری پزشکی مثل پویش‌های CAT و MRI، فشرده‌سازیMP3، دستکاری تصویر، هم‌نواسازی و هم‌گذری بلندگوهای با کیفیت بالا، و افکت صوتی برای تقویت‌کننده (الکترونیک) گیتار برقی است.

منبع

 

لینکدین چیست؟

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

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

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

ورود به صفحه شخصی شرکت بهسان اندیش در سایت لینکدین

 

صفحه شخیص شرکت بهسان اندیش در لینکدین

 

کانال شرکت بهسان اندیش در سایت اشتراک ویدئو آپارات (Aparat)

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

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

شرکت بهسان اندیش به منظور ارائه خدمات و فعالیت های خود در شبکه های اجتماعی اقدام به راه اندازی کانال شرکت بهسان اندیش در سایت آپارات نموده که علاقمندان می توانند از طریق لینک زیر در این سایت ما را دنبال کنید:

ورود به صفحه شخصی شرکت بهسان اندیش در سایت اشتراک ویدئو آپارات

 

شرکت بهسان اندیش در آپارات

www.aparat.com

مقدمه

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

دانلود کامل کاتالوگ (شامل تصاویر بیشتر جهت آشنایی با موضوع)

 

بینایی ماشین چیست؟

بینایی ماشین (به انگلیسی: Machine vision) شاخه‌ای از علم مهندسی است که به رشته‌های علوم کامپیوتری (Computer science) و علم نورشناسی و مهندسی مکانیک و اتوماسیون صنعتی ارتباط دارد. یکی از مهمترین و پر استفاده‌ترین کاربردهای آن در بازبینی و بررسی کالاهای صنعتی از جمله نیمه هادیها، اتومبیل‌ها، مواد خوراکی و دارو می‌باشد. همانند نیروی انسانی که با چشم غیر مسلح در خط تولید کالاها را برای تعیین کیفیت و نوع ساخت آنها بازبینی می‌کنند، Machine vision از دوربین‌های دیجیتال و دوربین‌های هوشمند و نرم‌افزارهای image processing (پردازش تصویر) برای این کار استفاده می‌کند. دستگاههای مربوطه (Machine vision) برای انجام دادن وظایفی خاص از جمله شمردن اشیاء در بالابرها، خواندن شماره سریالها(Serial numbers)، جستجوی سطح‌های معیوب به کار می‌روند.

بینایی ماشین و کنترل کیفیت

 

مزایای بهره گیری از بینایی ماشین در صنعت

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

 

کنترل کیفیت در صنعت

 

کاربردهای بینایی ماشین در صنعت

* بررسی مواد اولیه تولید (مثلاً کنترل کیفیت مواد اولیه).
* کنترل موجودی انبار و سیستمهای مدیریتی (شمارش، بارکد خواندن و ذخیره اطلاعات در سیستمهای دیجیتال)
* بررسی کیفیت محصول نهایی تولید شده
* کنترل کیفیت و بهبود محصولات غذایی.
* ماشینی کردن اجزای کوچک صنعتی.
* سیستمهای ایمنی موجود در محیط‌های صنعتی.
* کنترل رباتهای تعقیب خطی که برای حمل بار در کارخانه‌های صنعتی استفاده می‌شوند.

بینایی ماشین و کنترل کیفیت

 

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

اگرچه “بینایی ماشینی” بیشتر به عنوان یک فرآیند در کاربردهای صنعتی شناخته شده است، برای فهرست کردن اجزای سخت‌افزاری و نرم‌افزاری به کار برده شده نیز مفید می‌باشد. معمولاً یک بینایی ماشینی از اجزای زیر ساخته شده است:
1. یک یا چند دوربین دیجیتال یا آنالوگ (سیاه-سفید یا رنگی) با اپتیک مناسب برای گرفتن عکس.
2. واسطه‌ای که عکس‌ها را برای پردازش آماده می‌سازد. برای دوربین‌های آنالوگ این واسطه شامل یک دیجیتال کننده عکس است.

3. یک پردازشگر (گاهی یک PC یا پردازنده تعبیه شده (Embedded Processor) مانند DSP
4. نرم‌افزار Machine vision: این نرم‌افزار امکاناتی برای توسعه یک برنامه نرم‌افزاری که برای کاربردی مشخص شده است را فراهم می‌کند.
5. سخت‌افزار ورودی / خروجی (مثلاً I/O دیجیتال) یا حلقه‌های ارتباطی (مثلاً ارتباط شبکه ای یا RS-232) برای گزارش نتایج.
6. یک دوربین هوشمند: یک وسیله ساده که همه موارد فوق را داراست.
7. لنزهایی که بتواند به مقدار مطلوبی روی سنسور تصویر زوم کند.
8. منابع نوری مناسب و گاهی خیلی مخصوص (مثلاً چراغهای LED، فلورسنت، لامپهای هالوژن و . . .)
9. یک برنامهٔ مشخص که بتواند تصاویر را پردازش کرده و مشخصه‌های مربوط و مناسب را شناسایی کند.
10. یک سنسور همزمان ساز برای شناسایی اجزا (گاهی یک سنسور نوری یا یک سنسور مغناطیسی): این سنسور برای راه‌اندازی سیستمٍ استخراج و پردازش تصویر می‌باشد.

بهینه سازیبهینه‌سازی چیست؟

بهینه‌سازی یک مسئله ریاضی و کلی است که از قرن‌ها پیش مطرح بوده است و در حال حاضر هم یک مسئله و موضوع در دست بررسی و پژوهش است. هنوز راه حلی کلی برای تمام مسائل بهینه‌سازی مطرح نشده است. البته در بعضی موارد محدود که در آن تابع هدف کاملا مشخص شده و معین است و مسائلی مانند مشتق‌پذیری در آن وجود دارد؛ می‌توانیم بصورت دقیق آن را حل کنیم. در بعضی از مسائل هم جواب نهایی وجود دارد ولی زمان محاسبه آن بسیار زیاد طول خواهد کشید. با این حال هنوز برای بعضی از مسائل راه حل معقول و مشخصی ابداع نشده است. بر همین اساس، طبقه‌بندی‌های مختلفی برای اینگونه مسائل از لحاظ پیچیدگی و یا پارامترهای دیگر تعیین شده است. بطور مثال: مسائل برنامه‌ریزی خطی (LP)، برنامه‌ریزی غیر خطی (NLP)، مسائل درجه دوم (QP)، مسائل NP,NP-hard و…

بهینه سازی

مسئله فروشنده دوره‌گرد (TSP)

یکی از ساده‌ترین و در عین حال، پرکاربردترین و مفیدترین مسائل مطرح شده در حوزه بهینه‌سازی مسئله فروشنده دوره‌گرد (Traveling Salesman Problem) است.

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

این مسئله در طبقه‌بندی مسائل NP-hard قرار می‌گیرد و روش‌های عادی نمی تواند پاسخی برای این مسئله پیدا کند. اما بعضی از الگوریتم‌های فراابتکاری و یا تکاملی، می‌توانند در این خصوص پاسخ نه کاملا بهینه اما نزدیک به آن را به ما بدهند.

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

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

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

بهینه سازی

ارتباط بهینه‌سازی و الگوریتم‌های فراابتکاری

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

بهترین و کارآمدترین الگوریتم‌ها باید یک سری ویژگی‌ها را داشته باشند. بطور مثال: قابلیت کشف و جستجوی بالا (exploration) و قابلیت استخراج کردن (exploitation)

الگوریتم‌های بهینه‌سازی کلاسیک، اغلب این قابلیت‌ها را به صورت متعادل ندارند. بطور مثال قابلیت Global search برای استخراج کردن را ندارند. مکانیزم این گونه الگوریتم‌ها Local search است. همچنین الگوریتم‌های Random search (جستجوی تصادفی) در این بین هستند که Global search خوبی دارند ولی در نهایت نمی توانند به همگرایی مورد نیاز برسند. در واقع روشی که در بین این الگوریتم‌ها بصورت هوشمندانه عمل کند و در نهایت به همگرایی برسد، همان الگوریتمهای فراابتکاری و تکاملی است.

بهینه سازی

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

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

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

دیگر الگوریتم‌های فراابتکاری

الگوریتم‌های دیگری نیز در حوزه بهینه‌سازی و محاسبات تکاملی مطرح شده اند مانند: الگوریتم مورچگان (ACO)، الگوریتم ازدحام ذرات (PSO)، الگوریتم کلونی زنبور عسل (ABC)، الگوریتم رقابت استعماری (ICA) و …

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

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

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

منبع


منابع

1.http://bio1.ir

2.http://www.artaseminar.com

3.https://blog.faradars.org/

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

3-5-انواع روش‌هاي فرا ابتكاري برگرفته از طبيعت

1-3-5-الگوريتم ژنتيك

الگوريتم ژنتيك (Genetic Algorithm) روشي عمومي از روش‌هاي فرا ابتكاري براي بهينه‌سازي گسسته مي‌باشد كه مسائل جدول زمانبندي را حل مي‌نمايد. روش شبيه‌سازي كه در ادامه مورد بحث قرار می‌گيرد، راهبرد تكاملي نام دارد. اين روش در سال 1975 به وسيله هولند (Holland) و در سال 1989 توسط  گولدبرگ (Goldberg) ابداع شده است.

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

الف) يك موجود توانايي تكثير داشته باشد (قابليت توليد مثل).

ب) جمعيتي از اين موجودات قابل تكثير وجود داشته باشد.

پ) چنين وضعيتي داراي تنوع باشد.

ت) اين موجودات به وسيله قابليت‌هايي در زندگي از هم جدا شوند.

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

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

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

6- آنيلينگ شبيهسازي شده

اين روش توسط متروپوليس (Metropolis) و همكاران در سال 1953 پيشنهاد شده و جهت بهينه‌سازي به وسيله وچی (Vecchi)، گلات (Gelatt) و کرک‌پاتريک (kirkpatrick ) در سال 1983 مورد بازبيني قرار گرفته است. اين روش در مسائل تاكسي تلفني كاربرد دارد.

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

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

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

7-شبکه‌های عصبی

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

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

مدل پایه ای نرون

مدل پايه‌اي نورون به صورت شکل 1-3 تعريف می‌شود.

مدل پایه ای نرون

مدل پایه ای نرون

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

جستجوي ممنوع

روشی عمومي است كه به وسيله گلوور (Glover) در سال 1989 پيشنهاد شده و در حل مسائل برنامه‌ريزي كاري ـ خريد کاربرد دارد.

روش جستجوي ممنوع (Tabu Search)، همانند روش آنيلينگ شبيه‌سازي شده بر اساس جستجوي همسايه بنا شده است. در اين روش عملكرد حافظه انسان شبيه‌سازي شده است. حافظه انسان با به كارگيري ساختماني مؤثر و در عين حال ساده از اطلاعات، آنچه را در قبل رؤيت شده، ذخيره مي‌كند. اين مركز همچنين فهرستی از حركات منع شده را تنظيم مي‌كند و اين فهرست همواره بر اساس آخرين جستجوها منظم مي‌شود. اين روش از انجام هر گونه عمليات مجدد و تكراري جلوگيري مي‌كند.

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

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

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

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

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

سيستم مورچه (Ant System)

اين روش در سال 1991 توسط مانيه‌زو (Maniezzo) دوريگو (Dorigo) و کولورنی (Colorni) پيشنهاد شده است كه در حل مسأله فروشنده دوره‌گرد و مسائل تخصيص چندوجهي کاربرد دارد.

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

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

منبع


مقدمه ای بر بهینه سازی و الگوریتم های موجود

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

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

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

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

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

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

فرايند بهينه ­سازي

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

مدل­ سازي مسئله:

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

بهينه­ سازي مسئله:

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

استقرار مسئله:

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

الگوریتم­ های بهینه­ سازی

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

 روش‌هاي فرا ابتكاري برگرفته از طبيعت

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

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

–         استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري

–          استفاده از يك يا چند عامل (نرون، خرده‌ريز، كروموزوم، مورچه و غيره)

–          عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت

–          ايجاد روش‌هاي خود تغييري و خود تبديلي

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

1-    انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛

2-     جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.

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

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

1-    پديده‌اي حقيقي در طبيعت را مدل‌سازي مي‌كنند.

2-     بدون قطع مي‌باشند.

3-     اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.

4-     تطبيق‌پذير هستند.

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

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

 الگوریتم بهینه سازی ازدحام ذرات

در سال 1995 ابرهارت و کنیدی براي اولین بار PSOبه عنوان یک روش جستجوي غیر قطعی براي بهینه سازي تابعی مطرح گشت این الگوریتم از حرکت دسته جمعیپرندگانی که به دنبال غذا می­باشند، الهام گرفته شده است. گروهي از پرندگان در فضايي به صورت تصادفي دنبال غذا مي­گردند. تنها يك تكه غذا در فضاي مورد بحث وجود دارد. هيچ يك از پرندگان محل غذا را نمي­دانند. يكي از بهترين استراتژي­ها مي­تواند دنبال كردن پرنده­اي باشد كه كمترين فاصله را تا غذا داشته باشد.  ايناستراتژي در واقع جانمايه الگوريتم است. هر راه­حل كه به آن يك ذره گفته مي­شود،PSO  در الگوريتم معادل يك پرنده در الگوريتم حركت جمعي پرندگان مي­باشد.هر ذره يك مقدار شايستگي دارد كه توسط يك تابع شايستگي محاسبه مي­شود. هر چه ذره در فضا­ي جستجو به هدف – غذا در مدل حركت پرندگان-  نزدیكتر باشد،شايستگي بيشتري دارد. همچنين هر ذره داراي يك سرعت است كه هدايت حركت ذره را بر عهده دارد. هرذره با دنبال كردن ذرات بهينه در حالت فعلي، به حركت خوددر فضاي مساله ادامه مي­دهد.

الگوریتم کرم شب­ تاب

الگوریتم کرم شب ­تاب به عنوان الگوریتم ذهنی مبتنی بر ازدحام، برای وظایف بهینه­سازی محدود، ارائه شده است. در این الگوریتم از رفتار تابشی کرم­های شب تابالهام گرفته شده است. کرم­های شب تاب در طبیعت به طور دسته جمعی زندگی می­کنند و همواره کرم کم نورتر به سمت کرم پرنور تر حرکت می‌کند. این الگوریتم یکرویه تکراری مبتنی بر جمعیت را با عوامل بی­شمار (تحت عنوان کرم­های شب­تاب) به کار می‌گیرد. به این عوامل امکان داده می­شود تا فضای تابع هزینه را به صورتموثرتری نسبت به جستجوی تصادفی توزیع شده، بررسی کنند. تکنیک بهینه­سازی هوشمند، مبتنی بر این فرضیه است که راه­حل یک مشکل بهینه­سازی را، می­توان بهعنوان عاملی (کرم شب­تاب) در نظر گرفت که به صورت متناسب با کیفیت آن در یک محیط تابیده می­شود. متعاقباً هر کرم شب­تاب، همتایان خود را (صرف نظر ازجنسیتشان) جذب می­کند که فضای جستجو را به صورت موثرتری بررسی می­کند. الگوریتم­های کرم شب­تاب نورهای ریتمیک و کوتاه تولید می­کنند. الگوی نوری هر کدام از کرم­های شب­تاب با یکدیگر متفاوت می­باشند. الگوریتم­های کرم شب­تاب از این نورها به دو منظور استفاده می­کنند. 1- پروسه جذب جفت­ها 2- جذب شکار. به علاوه این نورها می­توانند به عنوان یک مکانیزم محافظتی برای کرم­های شب­تاب باشند.

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

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

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

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

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

واحد تحقیق و توسعه یا Research and Development که گاهی به صورت مخفف R&D هم مورد اشاره قرار می‌گیرد، بیش از نیم قرن است که به صورت جدی در سازمان‌ها، کسب و کارها و دولت‌ها مورد توجه قرار می‌گیرد.

حدود سالهای ۱۹۶۰ بود که برای نخستین بار، واحد تحقیق و توسعه به شکل جدی و رسمی در چارت سازمانی برخی شرکت‌ها مشاهده شد. البته طی دهه‌های بعد، تعریف واحد تحقیق و توسعه و وظایف واحد تحقیق و توسعه دچار اصلاحات و تغییراتی شد که در ادامه به آن اشاره می‌کنیم.

تعریف تحقیق و توسعه :

سازمان همکاری اقتصادی و توسعه (OECD) فعالیت تحقیق و توسعه را به صورت زیر تعریف می‌کند:

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

بهينه‌سازی يك فعاليت مهم و تعيين‌كننده در طراحي ساختاري است. طراحان زماني قادر خواهند بود طرح‌هاي بهتري توليد كنند كه بتوانند با روش‌هاي بهينه‌سازی در صرف زمان و هزينه طراحي صرفه‌جويي نمايند. بسياري از مسائل بهينه‌سازی در مهندسي، طبيعتاً پيچيده‌تر و مشكل‌تر از آن هستند كه با روش‌هاي مرسوم بهينه‌سازی نظير روش برنامه‌ريزي رياضي و نظاير آن قابل حل باشند. بهينه‌سازی تركيبي (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