بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
طراحی و ارزیابی یک الگوریتم مذاکره چندمعیاره در محیط چندعامله تجارت الکترونیکی
چکیده
در این مقاله با استفاده از تکنیکهای یادگیری الگوریتمی پیشنهاد شده است که طرفین مذاکره بدون در اختیار داشتن دانستههای اختصاصی حریف مقابل و با بهرهگیری از یک روش بروزشونده، حدسیات خود را در مورد علایق او تصحیح کرده و به یک مذاکرات چند معیاره برنده-برندۀ بهینه منجر میشود. بدین معنی که توافق در جایی حاصل میشود که هیچ حریفی نتواند پس از آن، پیشنهادی ارائه کند که بدون کم کردن سود حریف مقابل، سود خود را افزایش دهد. در این الگوریتم، عامل در زمان ارائه پیشنهاد خود، با استفاده از تکنیک مصالحه، پیشنهادات همارزش یا پیشنهاد پیشین خود را با جستجو در فضای جواب توسط یک الگوریتم ژنتیک، پیدا کرده و با بهرهگیری از مفهوم شباهت در تئوری فازی، از میان این مجموعه پیبشنهاد، پیشنهادی را برمیگزیند که بیشترین شباهت را با پیشنهاد اخیر حریف داشتهباشد. یافتن پیشنهاد دارای بیشترین شباهت با پیشنهاد حریف، مستلزم در اختیار داشتن تقریب بسیار خوبی از وزن اهمیت معیارهای پیشنهاد، از دید حریف میباشد که عملا جزء اطلاعات خصوصی وی محسوب میشود. استفاده از یادگیری بیز و مشاهدۀ رفتار حریف، این تقریب نزدیک به واقعیت را برای عامل فراهم میکند. عاملها، همچنین با استفاده از یادگیری Q و با مشاهدۀ بازخورد دریافتی از محیط، پارامترهای استراتژی خود را نظیر درصد تخفیف در پیشنهادات متوالی، را اصلاح میکنند. الگوریتم مذکور، پیادهسازی شده و از جهت داشتن کارآیی Pareto، پیچیدگی زمان و فضا و پایداری مورد ارزیابی قرار گرفته است.
واﮊه های کلیدی: مذاکره، مذاکره چند معیاره، سیستمهای چندعامله، مذاکره برنده-برنده
-1 مقدمه
موضوع مذاکره1 بین عاملها2 در زمینه های زیادی مطرح شده و به همین علت تعاریف مختلفی نیز برای آن پیشنهاد شده است.
تعریف ساده زیر را برای مذاکره میپذیریم.[1] مذاکره فرایندی است که در آن دستهای از عاملها با یکدیگر مکالمه کرده تا بتوانند به یک توافق دوجانبه بر روی چندین معیار دست پیدا کنند.در تجارت الکترونیکی، یک رابطه خریدار-فروشنده مطلوب را میتوان با مذاکرۀ چند معیاره برنده-برنده توصیف نمود. اهداف اصلی فروشنده عبارت است از سوددهی بلند مدت از طریق فروش هرچه بیشتر کالا به مشتریان هرچه زیادتر و با هزینه دادوستد هرچه پایین تر. اهداف اولیه مشتری نیز عبارت است از برآورده شدن نیازهای و سلایق شخصی در خرید کالای مناسب با هزینه کمتر. مذاکرۀ چند معیاره، در این فضا میتواند به برآورده شدن هرچه بهتر این دو دسته اهداف کمک کند. از دید فروشنده، این نوع مذاکره، پشنهادات او را با تکتک نیازمندیهای مشتری تطبیق داده که نتیجه آن، سوددهی بلند مدت فروشگاه خواهد بود. از دید مشتری نیز، مذاکرۀ چندمعیاره، به او در مقایسه و ارزیابی پیشنهادات مطرح شده از جانب فروشندگان در جنبههای مورد علاقه کمک میکند که نتیجه، رضایتمندی دو طرفه و یک خرید خالی از درگیری خواهد بود.
در این مقاله، روند طراحی یک الگوریتم مذاکره چندمعیاره بصورت گام به گام بررسی میشود. در این الگوریتم، عامل در زمان ارائه پیشنهاد خود، با استفاده از تکنیک مصالحه، پیشنهادات همارزش یا پیشنهاد پیشین خود را با جستجوی فضای جواب توسط یک الگوریتم ژنتیک، پیدا کرده و با بهرهگیری از مفهوم شباهت در تئوری فازی، از میان این مجموعه پیبشنهاد، پیشنهادی را برمیگزیند که بیشترین شیاهت را با پیشنهاد اخیر حریف داشتهباشد. یافتن پیشنهاد دارای بیشترین شباهت با پیشنهاد حریف، مستلزم در اختیار داشتن تقریب بسیار خوبی از وزن اهمیت معیارهای پیشنهاد، از دید حریف میباشد که عملا جزء اطلاعات خصوصی وی محسوب میشود. استفاده از یادگیری بیز و مشاهدۀ رفتار حریف، این تقریب نزدیک به واقعیت را برای عامل فراهم میکند. عاملها، همچنین با استفاده از یادگیری Q و با مشاهدۀ بازخورد دریافتی از محیط، پارامترهای استراتژی خود را نظیر درصد تخفیف در پیشنهادات متوالی، را اصلاح میکنند.
بخشهای مقاله بدین شکل تنظیم شدهاند: مروری بر کارهای انجام گرفته در حوزۀ مذاکرات بین عاملها در بخش دوم آوردهشده است. بخش سوم و چهارم اختصاص به تعاریف پایه ای بکار رفته در الگوریتم دارد و مفاهیم مصالحه و شباهت بصورت فرمال توضیح دادهشدهاند. در بخش پنجم، به فرضیات استفادهشده در الگوریتم پرداختهشده است. روند طراحی الگوریتم در بخشهای ششم، هفتم و هشتم بصورت گام به گام بررسی شده است. چگونگی تعیین پارامتر استراتژی مذاکرۀ عاملها در بخش نهم و ارزیابی و کارهای آتی نیز در بخشهای دهم و یازدهم آوردهشده است.
-2 مروری بر کارهای انجام گرفته
مذاکره در سیستمهای چندعامله را به دو دسته عمده میتوان تقسیمبندی نمود. مذاکرات همراه با یادگیری و مذاکرات بدون یادگیری. یکی از کاملترین مقالات در زمینه مذاکرات بین عاملها که از تکنیکهای یادگیری در آنها استفاده نشده است، مقاله [2]
میباشد. در این مقاله انواع تاکتیکهای مطرح نظیر تاکتیکهای وابسته به زمان، وابسته به منابع و وابسته به رفتار بصورت فرمال بررسی شدهاند. استفاده از تکنیک مصالحه3 در مذاکره، نیز یکی از روشهای کارآمد در مذاکرات برنده-برنده بحساب میآید که در [3] الگوریتمی بر این مبنا، ارائه و ارزیابی شده است.
مذاکرات همراه با یادگیری نیز در دو دسته تقسیمبندی میگردند. در یک دسته از این مذاکرات، استراتژی عامل مذاکرهکننده، در حین برهمکنش با حریف اصلاح و بروز میگردد. در دستهای دیگر، پس از اتمام روند مذاکره و با استفاده از بازخوردهای دریافتی، رفتار عامل اصلاح میشود. تکنیکهای یادگیری نظیر الگوریتمهای ژنتیک[4,5,6]، یادگیری بیز[7]، یادگیری [8] Q و درختهای تصمیمگیری[9] از عمده روشهای بکاررفته در این حوزه محسوب میشوند. تلفیق این تکنیکها با تئوری فازی[10] نیز در بهبود نتایج بسیار مؤثر بودهاست. این مقاله، گسترشی بر روش بکار رفته در مقاله [3] میباشد و بجای جستجوی فضای جواب توسط تولید پیشنهادات تصادفی که در آن مطرح شده، فضای جواب با استفاده از تکنیکهای الگوریتم تکاملی و یادگیری بیز، به نحو بهینهتری انجام میگیرد. در ضمن متغیرهای استراتژی حریفان نیز توسط یادگیری Q و یا تاکتیک وابسته به منابع، اصلاح میگیرد.
-3 فرمول بندی مصالحه
یکی از تکنیکهای عملی در پیادهسازی الگوریتمهای مذاکره برنده-برنده، انجام “مصالحه“ میباشد.[3] بدین معنی که طرف درگیر مذاکره، با رد پیشنهاد قبلی خود توسط حریف مقابل، امتیاز خود را در بعضی از جنبهها کاهش داده و همزمان در بعضی جنبههای دیگر، امتیاز خود را افزایش میدهد، بگونهای که امتیاز سر جمع پیشنهاد جدید برابر با امتیاز پیشنهاد پیشین باشد. با اتخاذ این شیوه توسط حریفان، احتمال برآوردن خواسته حریف مقابل وجود داشته، و حال آنکه خواسته خود حریف درگیر مذاکره نیز تامین میشود. این شیوه، پایه و اساس الگوریتم پیشنهادی را تشکیل میدهد.
زمانی یک عامل، به انجام مصالحه دست میزند که نخواهد سود خود را از سطح مور نظر ( ( θ پایین بیاورد. در ابتدا عامل، نیاز خواهد داشت، همه و یا بخشی از پیشنهادات دارای امتیاز θ را تولید کند. به بیان علمی، او نیاز دارد پیشنهادات واقع بر روی منحنی هم مقدارθ 4 را بدست آورد. از آنجا که این پیشنهادات از لحاظ سود عایدی برای عامل از ارزش یکسانی برخوردار هستند، از این حیث، هیچ تفاوتی بین آنها نیست. در الگوریتمهای مبتنی بر مصالحه، هدف پیدا کردن پیشنهادی است که بر روی منحنی هم مقدار پیشنهاد قبلی خود عامل واقع بوده و بیشترین سود را نصیب عامل طرف مقابل نماید. تعریف فرمال منحنی هم مقدار در ذیل آمدهاست:[3]
تعریف :1 فرض کنیم سود مورد نظر θ دادهشدهباشد. منحنی هممقدار در سطح θ برای عامل a که دارای تابع سودمندی v(x)
میباشد، بصورت زیر تعریف میگردد.
عامل باید از این مجموعه، پیشنهادی را انتخاب نماید که سود دو طرفه را بیشینه کند و یا بعبارت دیگر بیشترین سود را برای حریف در بر داشتهباشد زیرا در تمام نقاط این منحنی سود خود عامل ثابت است. از طرفی، عامل به تابع سودمندی حریف خود دسترسی ندارد و بطور قطعی نمیتواند تعیین کند که کدامیک از پیشنهادات فوق، برای حریف مقابل دارای بیشترین سود است.
بنابراین عامل مجبور خواهد بود دست به تقریب بزند.
بدیهیترین راهحلی که عامل در پیشرو دارد این است که پیشنهادی را انتخاب کند که بیشترین شباهت را با آخرین پیشنهاد ارائه شده از جانب حریف داشتهباشد. با این توصیف، میتوان از مفهوم “شباهت“ در سیستمهای فازی کمک گرفت و بصورت تقریبی میزان
نزدیکی دو پیشنهاد را به یکدیگر تعیین کرد. در ابتدا لازم است مفهوم شباهت را از دید سیستم فازی بررسی کنیم.[3]
تعریف: 2 دامنه مقادیر D j دادهشده است، شباهت بین دو مقدار x j, y j ∈ D j بدین شکل تعریف میگردد:
که در مجموعه جنبه های مقایسه میباشند و در آنها یک عملگر همارزی میباشد.
عملگر Λ نیز یک عملگر اتصال است که هر نوع تابع t-form میتواند انتخاب شود.
در کاربرد ما این عملگر همارزی به شکل زیر تعریف میگردد.
عملگر اتصال نیز عملگر کمینه((min انتخاب گردیدهاست. پس از تعریف میزان شباهت دو معیار، میتوان میزان شباهت دو پیشنهاد را تعریف کرد.[3]
تعریف :3 شباهت بین دو پیشنهاد x و y بر روی مجموعه معیارهای J عبارت است از:
که در آن تابع شباهت برای معیار j میباشد. w j وزن اهمیت معیار j است.
باید توجه داشت که در کاربرد ما، نیاز خواهد بود میزان شباهت بین آخرین پیشنهاد ارائه شده از طرف حریف و پیشنهاد انتخاب شده از میان پیشنهادات هم مقدار پیشنهاد پیشین، تعیین شود. این شباهت باید از دید حریف دیدهشود. بنابراین در تعریف فوق، وزن اهمیت معیارها( w j )، میزان اهمیتی است که گمان میرود عامل حریف برای معیارهای خود قائل است.
با توجه به تعاریف فوق، مصالحه را اینگونه میتوان تعریف نمود.[3]
تعریف: 4 فرض کنید پیشنهاد x از طرف عامل a به عامل b دادهشدهباشد و در مقابل پیشنهاد y از طرف عامل b به a ارائه شده باشد.
باشد، یک مصالحه برای پیشنهاد x عامل a، با توجه به پیشنهاد y عبارت است از:
-4 چگونگی محاسبه شباهت بین دو پیشنهاد
حال با توجه به تعاریف فوق و الزامات هستانشناسی5 مساله، لازم است شباهت بین دو پیشنهاد تعریف گردد. فرض میکنیم، هر پیشنهاد دارای سه معیار مقایسه میباشد، قیمت، کیفیت و زمان تحویل. بنابراین طبق تعریف 3، برای محاسبه شباهت بین دو پیشنهاد، ابتدا باید شباهت بین تکتک معیارها محاسبه شود. بعنوان مثال تعیین گردد که مقادیر معیار قیمت در دو پیشنهاد تا چه اندازه بهم شباهت دارند. برای این کار ،بنا بر تعریف 2، جنبههای مقایسه باید تعیین شود. مقایسه بین مقادیر هر معیار تنها بر روی یک جنبه انجام میگیرد، مقدار پیشنهادی آن معیار. بدین ترتیب، در تعریف 2 خواهیم داشت، . m 1
تابع h را بصورت زیر تعریف میکنیم:
همانگونه که مشاهده میگردد این تابع دارای پارامتر آزاد ε میباشد. هرچه پارامتر ε کوچکتر انتخاب شود، میزان تمایز بین مقادیر داخل بازۀ معیار (نسبت به مقادیر خارج از بازه) بیشتر و شیب منحنی برای آنها زیادتر میگردد. در آزمایشات بعمل آمده، بهترین نتایج با پارامتر،ε 0.3 حاصل شدند. تعیین ε برابر با 0.3 باعث ایجاد یک رفتار تقریبا خطی شده و میزان تمایز بین مقادیر، در طول بازه حالت خطی بخود میگیرد. در پیادهسازی، برای کلیه معیارها از تابع فوق استفاده گردیدهاست و
-5 فرضیات الگوریتم مذاکره
در ابتدا لازم است فرضیات الگوریتم شرح دادهشوند. همانگونه که قبلا نیز ذکر شد، هر کالا دارای مشخصات قیمت، کیفیت و زمان تحویل میباشد. در واقع این مشخصات، معیارهای مذاکره را معین میکنند. تابع ارزش معیارها، بصورت زیر تعریف میگردد.
افزایشی و یا کاهشی بودن، جهت تغییر ارزش را زمانیکه معیارمیافزایش پیدا میکند، نشان دهد. بعنوان مثال معیار قیمت برای فروشنده، افزایشی و برای خریدار، کاهشی خواهد بود. تابع سودمندی هر عامل نیز بصورت جمع وزنی ارزش معیارها، تعریف میگردد
و همچنین شباهت دو پیشنهاد نیز طبق تعریف ٣ و توسط تابع ذکر شده در بخش (٤) سنجیده میشود.
-6 الگوریتم اول:مصالحه با پیشنهادات تصادفی
در الگوریتم اول، هر عامل در صورت نپذیرفتن پیشنهاد حریف، بصورت تصادفی تعدادN پیشنهاد تولید میکند. خصوصیت مشترک کلیه این پیشنهادات در این است که میزان ارزش آنها (مقداری که توسط تابع سودمندی عامل تعیین میشود) نسبت به پیشنهاد قبلی همین عامل، بصورت درصدی دقیقا باندازه متغیر consession کمتر است. بعبارت دیگر متغیر consession، درصد تخفیف را تعیین میکند. حال از بین این پیشنهادات، پیشنهادی انتخاب می گردد که بیشترین شباهت را با پیشنهاد حریف داشته باشد. رسیدن به این هدف، مستلزم آن است که در بهترین حالت، وزن معیارهای حریف مشخص باشد و یا اینکه بتوان تقریب خوبی از آن، بدست آورد. شرط پایان الگوریتم، این است میزان ارزش پیشنهاد حریف، از ارزش پیشنهاد بدست آمده بیشتر باشد. در این صورت پیشنهاد حریف پذیرفته میشود. شبه کد این الگوریتم در شکل1 آمدهاست.
در این الگوریتم، wjo وزن معیار j از دید حریف میباشد و این بدین معنا است که هر حریف وزن معیارهای حریف مقابل خود را میداند. این فرض نمیتواند، فرض درستی باشد اما میتواند نقطه شروع خوبی بحساب آید. شکل((2 نمونهای از اجرای این الگوریتم را به تصویر کشیدهاست. همانگونه که در شکل((2 دیده میشود، نتایج حاصله دارای کارآیی pareto میباشند. اما این نتایج در شرایطی حاصل شدهاند که وزن معیارهای دو حریف نزدیک به یکدیگر بودهاند. نزدیکی وزن معیارهای حریفان، باعث خواهد شد، ناحیه جواب باریک شده و پیشنهادات تصادفی بتوانند، بخوبی آنرا پوشش دهند. اما زمانیکه این وزنها تفاوت زیادی با هم داشتهباشند، ناحیه جواب بزرگ شده و امکان پوشش این ناحیه با تعداد کم نقاط تصادفی امکانپذیر نخواهد بود شکل(.(3 با افزایش تعداد نقاط تصادفی میتوان، احتمال پوشش کامل این ناحیه را افزایش داد. در اینجا، انتخاب مقدار پارامتر N بسیار با اهمیت است-این پارامتر، تعداد پیشنهادات تصادفی تولید شده توسط عامل را نشان میدهد که در نهایت یکی از آنها بعنوان پیشنهاد اصلی انتخاب میگردد. درستی این ادعا را در شکلهای (3) و (4) میتوان دید. در این آزمایشات، وزن معیارهای حریفان از یکدیگر دورتر انتخاب شده است. شکل((3 نتیجه حاصل را با انتخاب N=1000 و شکل((4 با انتخاب N=5000 به تصویر کشیدهاست. همانگونه که انتظار میرفت، افزایش پارامتر N در بهبود نتیجه حاصل مؤثر بودهاست. با نگاهی به بحث، می توان دریافت، هدف اصلی، جستجوی یک فضای گسترده برای رسیدن به جواب بهینه میباشد. این فضا عبارت است از کلیه پیشنهادات ممکن که سودمندی آنها اندکی کمتر از سودمندی آخرین پیشنهاد رد شده توسط حریف بوده و بیشترین شباهت را با پیشنهاد جدید او داشتهباشد. با این داشتهها، الگوریتهای ژنتیک میتوانند گزینه مناسبی بحساب آیند. در عمل، الگوریتمهای ژنتیک بهترین انتخاب برای مسایل دارای فضای جستجوی گسترده بهمراه اطلاعات ناکافی از محیط، بحساب می آیند و در حوزۀ کاربرد ما نیز این تکنیک میتواند مثمر ثمر باشد. از یک سو جستجوی فضای گسترده را برای یافتن جواب بهینه کارآمدتر نموده و از سویی دیگر ما را از یافتن معکوس توابع معکوس ارزش معیارها بی نیاز میکند. اما باید به این نکته توجه داشت که تنظیم متغیرهای الگوریتمهای ژنتیک – اندازه جمعیت، اندزۀ کروموزمها و ژنها و نرخ همگذری و یا نرخ جهش- در حجم محاسبه، نرخ همگرایی و میزان دقت نتایج حاصل بسیار تعیینکننده میباشند.
-7 الگوریتم دوم : جستجو با الگوریتم ژنتیک
در این الگوریتم، جستجوی فضای جواب و پیدا کردن جواب بهینه از حالت تصادفی خارج شده و توسط یک مکانیزم تکاملی انجام میگیرد. در این بخش به شرح جزئیات این الگوریتم میپردازیم.بازای هر معیار مذاکره یک ژن در نظر گرفتهشده است. بدین ترتیب در سناریوی ما، هر کروموزوم شامل سه ژن متناظر به معیارهای قیمت، کیفیت و زمان تحویل خواهد بود و در واقع هرکروموزوم یک پیشنهاد را نشان میدهد. پس از تعیین طول هر ژن و تعیین نرخهای همگذری و جهش، باید تابع شایستگی مشخص گردد. این تابع بشکل زیر تعریف شده است:
در این تابع، xn پیشنهاد پیشین عامل و yn پیشنهاد جدید حریف میباشد. در بخش اول این تابع، تفاوت ارزش پیشنهاد مورد نظر و ارزش پیشنهاد نهایی – که در واقع ارزش پیشنهاد پیشین منهای میزان تخفیف میباشد- کمینهشده و بانتیجه بخش اول بیشینه میگردد و در بخش دوم نیز میزان شباهت با پیشنهاد اخیر حریف، بیشینه میگردد. پارامتر β در این تابع، دو نقش را ایفا میکند (1
اولویت زیادتری به بخش مضروب فیه خود میدهد بعبارت دیگر شایستگی پیشنهاداتی را که از لحاظ ارزش به پیشنهاد نهایی نزدیک هستند، بیشتر از پیشنهادات نزدیک به پیشنهاد حریف، خواهد نمود (2 تداخل در محاسبات دو بخش تابع را برای رسیدن به نقطه بیشینه کل تابع را از بین میبرد. در الگوریتم پیشنهادی شده مقدار پارامتر β برابر 10 در نظر گرفتهشده است. در آزمایشات بعمل آمده طول هر ژن 15 بیت میباشد. از همگذری دو نقطهای استفاده و نرخ جهش برابر با عکس حاصلضرب تعداد ژنها در اندازۀ آنها در نظر گرفته شده است. شبهکد الگوریتم در شکل (5) آوردهشده است. نتایج حاصل از این الگوریتم در شکلهای (6) و (7) و (8) نشان
داده شده است. همانگونه که در این شکلها دیده میشود، افزایش در اندازۀ جمعیت و تعداد نسل، در بهبود نتایج حاصله مؤثر میباشد.
