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

توضیحات

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

عنوان انگلیسی مقاله ترجمه شده:

Personalized Search Inspired Fast Interactive Estimation of Distribution Algorithm and Its Application

  

چکیده

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

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

1- مقدمه

محاسبات تکاملی (فرگشتی) (EC)[1]، با تقلید از قواعد طبیعی تکامل، روشی قدرتمند برای حل مسائل بهینه‌سازی پیچیده هستند. یک تابع مناسب مرتبط با مساله بهینه سازی، اساس EC را با «بقای اصلح» تشکیل می‌دهد، و کاندیداهای با صلاحیت بالاتر، برای تکامل بیشتر انتخاب می‌شوند. اگرچه، توصیف برخی مسائل با مدل‌های ریاضی دقیق، غیرممکن است. در بهینه‌سازی‌های شخصی، مانند طراحی محصول، طرح‌بندی خانه و جستجوی شخصی، می‌بایست راه‌حل‌ها ارزیابی شده و توسط کاربران مطابق با اولویتشان، انتخاب شوند. در چنین سناریوهایی، تخصیص مناسب راه‌حل‌ها، شخصی و نسبی است بطوری‌که ارزیابی برخی راه‌حل‌ها، می‌تواند تحت شرایط مختلف، بسیار متفاوت باشد. بر این اساس، EC مرسوم کاربرد وسیعی نداشته و می‌بایست با ارزیابی‌های کاربر منطبق شود.

محاسبات تکاملی تعاملی (IEC)[2]، با در نظر گرفتن ارزیابی‌های کاربر در فرآیند تکامل، بطور موفقیت آمیزی توسعه یافته و در مسائل بهینه‌سازی شخصی مختلف نظیر طراحی محصول، طراحی صفحه وب و طراحی وسایل نقلیه ضد تصادف بکار گرفته شده است. در مقایسه با EC مرسوم در بهینه‌سازی تعریف شده با توابع ریاضی، IEC به کاربری نیاز دارد که راه‌حل‌ها را ارزیابی کند و به‌ناچار در هنگام ارزیابی، لازم است مسئولیت تمام ارزیابی‌ها به کاربر سپرده شود. معمولا، اندازه جمعیت و نسل‌های تکامل یافته IEC، بخاطر خستگی کاربر به مقادیر کوچک محدود هستند که قدرت اکتشافی IEC در حل مسائل پیچیده را بطور قابل توجهی کاهش می‌دهد. بنابراین، باید توجه بیشتری به کاهش خستگی کاربر و بهبود اکتشاف IEC شود.

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

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

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

مکانیزم‌های تکاملی قدرتمند دیگر نظیر تخمین الگوریتم‌های توزیع (EDAs)[3]، ثابت کرده‌اند که در بسیاری از مسائل بهینه‌سازی پیچیده با ادغام مدل‌های یادگیری احتمالی و GA، عملکرد بهتری از GA دارند. حوزه دانش که اولویت کاربر را در جستجوی شخصی منعکس می‌کند، می‌تواند برای کمک به جستجو با تمرکز بر زیرفضای ارجح، بسیار با ارزش باشد بطوری‌که اپراتورهای IEC را افزایش می‌دهد. اگر این مسائل بیشتر مورد بررسی قرار گیرند، کارایی IEC با مد‌های ارزیابی ضمنی، بطور قابل توجهی بهبود می‌یابد. در این راستا، در اینجا یک جستجوی شخصی که به تخمین تعاملی الگوریتم توزیع تحت مد ارزیابی ضمنی با حوزه‌ی دانش (PS-IEDA-DK) برای یافتن سریع کاندیداهای رضایت بخش با خستگی کاربر کمتر کمک می‌کند، توسعه داده می‌شود.

در الگوریتم پیشنهادی، ابتدا مدل احتمالی اولویت کاربر بر روی متغیرهای بهینه‌شده از سوابق جستجوی شخصی با استفاده از تخمین بیزی ساده، استخراج می‌شود. سپس، از مدل بیزی برای کاهش فضای جستجوی اولیه‌ی مساله بهینه‌سازی به یک زیرفضای اولویت‌دار برای تسریع فرآیند جستجوی ورودی، استفاده می‌شود. به‌علاوه، یک EDA تعاملی با اشخاص ابتدایی با مدل احتمالی اولویت اولیه بر روی متغیرها، پیشنهاد می‌شود. برای تکامل موفقیت آمیز، تخمین تناسب با ایجاد یک شبکه با تابع پایه شعاعی (RBF)[4] بعنوان جایگزینی با ارزیابی‌های تعاملی، انجام گرفته است. انتظار می‌رود که این الگوریتم، راه‌حل‌های رضایت‌بخش را با کمترین خستگی کاربر، پیدا کند. توزیع‌های اصلی این الگوریتم به صورت زیر هستند: 1- حوزه دانش درمورد اولویت کاربری درگیر در متغیرهای بهینه‌شده، از اطلاعات آماری با استفاده از مدل بیزی ساده استخراج می‌شود؛ 2- فضای اکتشاف اولیه از IEDA طراحی‌شده، با حوزه‌ی اولویت کاربر منطبق می‌شود؛ 3- با درنظر گرفتن احتمال اولویت بر روی متغیرها، IEDA با یک جانشین RBF که بخوبی آموزش دیده، طراحی شده و بهبود می‌یابد.

سایر قسمت‌های این مقاله بصورت زیر پیکربندی شده است. بخش (2)، کارهای مرتبط با EDA و جستجوی شخصی با بهینه‌سازی تکاملی، شرح داده می‌شوند. چارچوب الگوریتم پیشنهادی در بخش (3) ارائه شده است. همچنین، در این بخش، جزئیات IEDA بهبودیافته، بخصوص استراتژی کاهش فضای جستجو بر اساس تخمین بیزی ساده، آماده‌سازی جمعیت و جایگزینی اولویت، بیان می‌شود. در بخش (4)، کاربردهای الگوریتم پیشنهادی همراه با نتایج آزمایشی و تحلیل‌ها، آورده شده است. نتیجه‌گیری در بخش (5) ارائه شده است.

2- کارهای مرتبط

2-1- تخمین الگوریتم توزیع

EDA‌یی که در ابتدا توسط مولنبین و پاب ]13[ پیشنهاد شد، یک حالت بهینه‌سازی تکاملی جدید با ادغام الگوریتم‌های ژنتیک و یادگیری آماری است. این روش، اطلاعات وسیعی در مورد جمعیت با ایجاد یک مدل احتمالی واضح از راه‌حل‌های امیدوارکننده آن‌ها، ارائه می‌کند. سپس، فرزند با نمونه‌برداری از مدل احتمالی، متولد می‌شود. EDA بطور گسترده‌ای برای مسائل مختلف نظیر مساله جدول‌بندی مسیرهای جایگشت بدون جابجایی (NIPFSP)[5]، مساله جدول‌بندی وظایف تصادفی دو معیاره با نامعینی در زمان پردازش، مساله عملیات کنترل مخزن چند هدفه روخانه‌ها (MO-RFCO)[6] و مسائل درخت اشتاینر موجود در حمل و نقل، شبکه‌های ارتباطی، مهندسی بیولوژیکی و مسائل مسیرسازی چندرسانه‌ای QoS، بکار گرفته شده است. اما، EDA برای چارچوب IEC و جستجوی شخصی، بکارگرفته نشده است.

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

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

بدیهی است که، تعریف مدل احتمالی، امری لازم است. با استفاده از مدل‌های احتمالی، EDA‌ها توانایی معرفی اطلاعات پیشین در مورد بهینه‌سازی برای امکان‌پذیری استفاده از آمار بیزی را دارند. استفاده از اطلاعات پیشین بررسی شده و در بهینه‌سازی استفاده شده است. دو منبع در EDA‌ها قابل گنجاندن است: 1- دانش پیشین و 2- اطلاعات حاصل شده از EDA پیشین که در مسائل مشابه دیگر اجرا شده‌اند؛ این دو می‌توانند با آمار بیزی یا دیگر روش‌ها نیز ترکیب شوند. الگوریتم این مقاله، بر اساس حوزه‌های دانش استخراج شده از اولویت کاربر بعنوان دانش پیشین عمل می‌کند و از آن برای افزایش EDA استفاده می‌کند.

2-2- جستجوی شخصی با الگوریتم‌های تکاملی

در جستجوی شخصی، مدل‌سازی یا دنبال‌کردن اولویت کاربر براساس تعاملات انجام گرفته توسط کاربران است. چانگ و همکاران]25[، شبکه‌های اولویت شرطی (CP-nets) برای تشریح اولویت کاربر براساس سوابق جستجو را ایجاد کردند و سپس از شبکه CP برای فیلتر کردن نتایج جستجو استفاده کردند. کاساک و همکاران ]26[، یک مدل اولویت کاربر را با استفاده از بازخوردهای صریح و ضمنی نظیر رتبه و زمان گذرانده شده برای آیتم‌ها، ارائه کردند. برای توصیه پویا تحت شرایط داده‌های جایگزین، تانگ و همکاران ]27[، یک الگوریتم توصیه شخصی پویای جدید پیشنهاد کردند که در آن، اطلاعات موجود در  محتوای نمایه و رتبه، با بررسی ارتباط پنهان میان رتبه‌بندی‌ها، استخراج می‌گردد. تمام این پژوهش‌ها، بر روی فرآیند مدل‌سازی اولویت بدون در نظر گرفتن بهینه‌سازی، تاکید کرده‌اند.

برخی پژوهش‌ها، برای حصول مدل‌های اولویت قابل اطمینان، EA‌ها را برای بهینه کردن ساختار یا پارامترهای مدل‌های اولویت معرفی کرد‌ه‌اند. شاکر و همکاران ]28[ یک رویکرد جدید برای یادگیری اولویت زوج با ترکیب یک روش تکاملی با جنگل تصادفی، پیشنهاد کردند. آن‌ها در ادامه، روشی را با بیان اسپلاین رگرسیونی تطبیقی چند متغیره (MARS)[7] در بهینه‌سازی تکاملی برای یادگیری اولویت زوج، ارائه کردند. کوزما و همکاران ]30[، امکان سنجی شبکه‌های عصبی برای پیش‌بینی اولویت کاربر با گنجاندن یک IEC را مورد بررسی قرار دادند. این پژوهش‌ها، اساسا بر روی بکارگیری الگوریتم‌های تکاملی برای بهینه‌سازی پارامترهای مدل‌های اولویت کاربر بجای جستجوی خودش، تمرکز کرده‌اند.

برای ترکیب IGA با محتوای فیلتر شده، کیم و همکاران ]31[ یک سیستم توصیه‌کننده ابتکاری که بطور پویا، اولویت کاربر در مورد موزیک را دنبال می‌کند، ارائه کردند. آن ]32[، از یک مدل عاملی برای تقلید رفتار منطقی کاربر استفاده کرد و سپس یک استراتژی تکامل با مدل عاملی برای جستجوی رفتار منطقی یک کاربر، اتخاذ کرد.

برای مقابله با توصیه‌های مبتنی بر محتوا، کانت و همکاران ]33[ از روش‌های مستثنی (RMs)[8] برای رسیدگی به نامعینی‌ها استفاده کردند و IGA را برای بازیابی اطلاعات بکار گرفتند.

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

توجه:

• برای دانلود فایل word کامل ترجمه از گزینه افزودن به سبد خرید بالا استفاده فرمایید.
• لینک دانلود فایل بلافاصله پس از خرید بصورت اتوماتیک برای شما ایمیل می گردد.

سفارش ترجمه مقاله

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

سفارش ترجمه تخصصی