• • استفاده از «الگوریتم‌های مکاشفه‌ای»^[۳۱] که جواب‌هایی به دست می‌دهد که احتمالاً درست هستند.

  

• پیدا کردن زیرمسأله‌هایی از مسأله، یعنی تقسیم مسأله به مسأله‌های کوچکتر.

دو مسألۀ زیر جزءِ مسائل NP-Hard می‌باشند:

• • مسئله فروشنده دوره‌گرد

• مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل)^[۳۲]

اما مسائل مهم زیادی نیز وجود دارند که یافتن راه‌حل در آن­ها بسیار دشوار است. اما اگر راه‌حل را داشته باشیم، بررسی آن آسان می‌شود. این واقعیت منجر به مسائل NP-Complete problems شد.NP معرفNondeterministic (چند جمله‌ای‌های غیرجبری) و ‌به این معنا است که امکان این وجود که راه‌حل را حدس زد و سپس آن را بررسی کرد.

برای سهولت کار، بررسی مسائل NP-Complete ، محدود به مسائلی است که پاسخ می‌تواند بله یا خیر باشد. به دلیل وجود کارهایی با نتایج پیچیده، دسته دیگری از مسائل با نام NP-Hard معرفی شده‌اند. این دسته مانند مسائل NP-Complete محدود نیستند.

یکی از ویژگی‌های مسائل NP آن است که یک الگوریتم ساده را (که ممکن است در نگاه اول بدیهی به نظر برسد) می‌توان برای یافتن راه‌ حل ‌های مفید به کار برد. اما به طور کلی، این روش، روش‌های ممکن زیادی را فراهم می‌کند و بررسی کردن تمام راه ‌حل ‌ها، فرایند بسیار کندی خواهد بود.

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

۲-۴-۳- هیوریستیک^[۳۳]

سیستم‌های پیچیده اجتماعی، تعداد زیادی از مسائلِ دارایِ طبیعتِ ترکیباتی را پیش روی ما قرار می‌دهند. مسیر کامیون‌های حمل‌ونقل باید تعیین شود، انبارها یا نقاط فروش محصولات باید جایابی شوند، شبکه های ارتباطی باید طراحی شوند، کانتینرها باید بارگیری شوند، رابط‌های رادیویی می‌بایست دارای فرکانس مناسب باشند، مواد اولیه چوب، فلز، شیشه و چرم باید به اندازه های لازم بریده شوند؛ از این دست مسائل بی‌شمارند. تئوری پیچیدگی به ما می‌گوید که مسائلِ ترکیباتی اغلب چندجمله‌ای^[۳۴] نیستند. این مسائل در اندازه های کاربردی و عملی خود به قدری بزرگ هستند که نمی‌توان جواب بهینۀ آن­ها را در مدّت زمان قابل پذیرش به دست آورد. با این وجود، این مسائل باید حل شوند و ‌بنابرین‏ چاره‌ای نیست که به جواب‌های زیر بهینه بسنده نمود؛ به گونه‌ای که دارای کیفیّت قابل پذیرش بوده و در مدّت زمان قابل پذیرش به دست آیند. چندین رویکرد برای طراحی جواب‌های با کیفیّت قابل پذیرش تحت محدودیّت زمانی قابل پذیرش پیشنهاد شده است. الگوریتم‌هایی وجود دارند که می‌توانند یافتن جواب‌های خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به آن­ها الگوریتم‌های تقریبی می‌گویند. الگوریتم‌های دیگری هستند که تضمین می‌دهند با احتمال بالا جواب نزدیک بهینه تولید کنند که به آن­ها الگوریتم‌های احتمالی گفته می‌شود. جدای از این دو دسته، می‌توان الگوریتم‌هایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آن­ها، به طور متوسط بهترین تقابل کیفیت و زمان حل برای مسأله مورد بررسی را به همراه ‌داشته‌اند؛ ‌به این الگوریتم‌ها، الگوریتم‌های هیوریستیک گفته می‌شود.

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

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

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

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

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

در حالت کلی سه دسته از الگوریتم‌های هیوریستیک قابل تشخیص است:

• • • الگوریتم‌هایی که بر ویژگی‌های ساختاری مسأله و ساختار جواب متمرکز می‌شوند و با بهره گرفتن از آن­ها الگوریتم‌های سازنده یا جستجوی محلی تعریف می‌کنند.
  • • الگوریتم‌هایی که بر هدایت هیوریستیک یک الگوریتم سازنده یا جستجوی محلی متمرکز می‌شوند به گونه‌ای که آن الگوریتم بتواند بر شرایط حساس (مانند فرار از بهینه محلی) غلبه کند. ‌به این الگوریتم‌ها، متاهیوریستیک^[۳۵] گفته می‌شود.
  • الگوریتم‌هایی که بر ترکیب یک چارچوب یا مفهوم هیوریستیک با گونه‌هایی از برنامه‌ریزی ریاضی (معمولا روش های دقیق) متمرکز می‌شوند.