بخشی از مقاله
بررسي بهينگي طراحي نقاط کنترل مسطحاتي در شبکه هاي فتوگرامتري هوايي
چکيده :
طـراحي بهيـنه نقـاط کنـترل عکسـي در فرآيـند مثـلث بـندي هوايـي امري پيچيده بوده و به پارامترهاي زيادي در قبل و بعد از مثـلث بـندي هوايـي بسـتگي دارد. روندهـاي کلاسيک صرفا با استفاده از آزمونهاي بيشمار سعي و خطا، اصولي را در طراحي بهينه نقاط کنترل دريافته اند که هنوز اين مساله از ديدگاه بهينه سازي مورد تجزيه و تحليل دقيق قرار نگرفته است . در اين راستا بررسي هاي کلاسيک انجـام شـده نشـان داده است که وجود نقاط کنترل مسطحاتي فقط در اطراف بلوک کاملا کافي بوده و مطلقا احتياجي به وجود اين سري نقـاط در ميـان بلوک نخواهد بود. براي بررسي اين اصل ، در اين تحقيق محل و تعداد نقط کنترل مسطحاتي مجهول درنظر گرفته شد و با اسـتفاده از ابـزارهاي بهيـنه سـازي ، نسبت به تعيين وضعيت بهينه نقاط کنترل اقدام گرديد. توابع مطلوبيت در اين حالت دقت ، يکنواختي توزيع خطا و تعداد نقاط کنترل در نظر گرفته شدند.در روش ارائه شده در اين نوشته ، با استفاده از الگوريتمهاي تکاملي به بررسي طراحي بهيـنه نقـاط کنـترل مسـطحاتي در مثلث بندي هوايي پرداخته و از ديدگاه بهينه سازي نشان داده مي شود که اصل مذکور بهينه ترين حالت ممکن مي باشد.
واژگان کليدي : مثلث بندي هوايي ، طراحي نقاط کنترل مسطحاتي ، بهينه سازي سراسري ، الگوريتمهاي تکاملي .
۱- مقدمه
در پـروژه هـاي فتوگرامـتري هوايـي عمومـاً بـلوکي از عکـس هـاي پوشش دار به منظور اندازه گيري هندسي عـوارض زميـني بکـار گرفته ميشوند. جهت زمين مرجع نمودن اين بلوک عکسي با حداقل هزينه عمليات زميني ، از تعدادي محدود از نقاط کنترل زميني به همراه مشاهدات نقاط گرهي بين عکسها استفاده مي گردد که با گذر از فرآيند مثـلث بـندي هوايـي ، مختصات زميني تمامي نقاط اندازه گيري محاسبه مي گردد. دقت مختصات زميني محاسبه شده نقاط که به دقت مثلث بندي معروف است ، تاثير مستقيم در دقت عوارض هندسي استخراجي از عکسها دارد.
دقـت مثـلث بـندي وابسته به عوامل متعدد شامل : مشخصات سيستم عکسبرداري هوايي ، دقت ، نوع ، تعداد و پراکندگي نقاط کنترل زميني و نقاط گرهي عکسي ، دقت و نوع دستگاه اندازه گيري مشاهدات عکسي ، وجود يا عدم وجـود مشـاهدات کمکي ، متد مثلث بندي هوايي ، روش سرشکني و فيلترينگ خطاها، مقياس عکس و پوشش آنها و نـوع و مقيـاس نقشـه درخواستي ميباشد. تعدادي از اين پارامترها بواسطه محدوديتهاي اجرايي ، معين و ثابت بوده و مـواردي همچون طراحي نقاط کنترل زميني نقش مهمي را در رسيدن به دقت مثلث بندي موردنياز با توجه به حداقل هزينه عمليات زميني (تعداد، نوع و محل نقاط ) ايفا مي نمايد(۱}.
از ديدگـاه سرشـکني ، دقـت مثلث بندي وابسته به دو پارامتر خطاي مختصات عکسي و فاکتور هندسي است کـه مـبين اسـتحکام هندسي شکل شبکه مثلث بندي است . مورد اول وابسته به دقت تهيه ، نوع نقاط عکسي و روش ، نوع و دقت دستگاه اندازه گيري آنها است درحاليکه مورد دوم وابسته به نوع ، تعداد و پراکندگي نقاط کنترل زميني و نقـاط گـرهي عکسـي ، ابعـاد و وضـعيت عکسها و نوارهاي عکسبرداري و پوشش طولي و عرضي عکسها دارد. اين مساله در رابطه اساسي ۱ نشان داده شده است که در آن V دقت مطلق مثلث بندي ، Vo دقت اندازه گيري مختصات عکسي وQ ضريب استحکام هندسي شکل شبکه است (۱۹}.
طـبق تحقيقـات صورت گرفته توسط محققان و ارگان هاي متفاوت مطرح در زمينه فتوگرامتري ، طراحي نقاط کنـترل مسـطحاتي و ارتفـاعي دو امـر تقريـبا مستقل بوده و بواسطه استحکام مسطحاتي بالاتر شبکه هاي فتوگرامتري هوايي بعلت پوششهاي طولي و عرضي بين عکسها و مشاهده نقاط گرهي مشترک بين آنها، به نقاط کنترل مسطحاتي کمـتري نيـاز ميباشـد. عـلاوه بـر ايـن توزيـع نقـاط کنـترل مسـطحاتي و ارتفاعي متفاوت از هم بوده و نقاط کنترل مسـطحاتي تنها در پيرامون بلوک مورد نياز مي باشند درحاليکه نقاط کنترل ارتفاعي بايستي در سرتاسر شبکه بصورت يکـنواخت در بيـن نوارهـا توزيـع شـده باشـند. تحقيقـات همچـنين نشـان ميدهد که حتي اضافه کردن نقاط کنترل مسـطحاتي در وسـط شـبکه نـه تـنها دقـت را افزايش نداده بلکه بواسطه خطاهاي موجود موجب يکنوع ناسازگاري دروني شده و باعث کاهش دقت در نتايج مي گردد.
اگـرچه نتايج فوق با گذر از آزمايشات فراوان صحت خود را درعمل به اثبات رسانيده است اما هنوز تحقيقي دقيـق و عـلمي بـر اسـاس مفاهيم بهينه سازي ، بهينه بودن اين نوع طراحي را به اثبات نرسانده است . هدف اصلي از تحقيق انجام شده در اين نوشته تعيين ميزان بهينگي طراحي فوق مي باشد.
از ديدگـاه بهينه سازي در مساله طراحي نقاط کنترل مثلث بندي ، نوع ، تعداد و پراکندگي نقاط کنترل مجهول بـوده و بايستي وضعيتي را براي آنها جستجو نمود که يک تابع مطلوبيت را که شامل اندازه و پراکندگي خطا و تعداد نقـاط کنترل ميباشد بهينه نمايد. در اين بهينه سازي هدف يافتن بهينه مطلق و نه موضعي است . بعبارت ديگر وضعيت بهينه اي مورد نظر است که از تمامي حالات ديگر بهتر باشد.
از بيـن روشـهاي متـنوع موجود در زمينه بهينه سازي سراسري (optimization goba١١)، در اين تحقيق روش مبتـني بـر الگوريـتمهاي تکامـلي بکارگرفـته شـده است . علت اين امر در قابليت هاي بالاي اين روش در مواجهه با مسـايل پيچيـده (np-iiard probem١) مشـابه وضـعيت مطرح در مساله مورد بحث در اين تحقيق مي باشد. ذکر اين نکـته لازم اسـت کـه در اين تحقيق براي سادگي کار و امکان آناليز نتايج حاصل در مراحل مختلف پردازشي ، از يک شبکه مسطحاتي شبيه سازي شده استفاده گرديده و طراحي بهينه نقاط کنترل مسطحاتي با گذر از فرايند بهينه سازي در آن صورت گرفته است .
۲- بهينه سازي سراسري
مفهـوم بهيـنه سـازي سراسـري عبارتسـت از رسـيدن بـه بهترين تصميم ممکن از بين يک مجموعه وضعيت موجـود(۲۲}. از ديدگـاه رياضـي ، يک مساله بهينه سازي سراسري سعي در يافتن حداکثر و حداقل مقدار مطلق يک تـابع (بـنام تـابع مطـلوبيت ) دارد(۶}. بـراي اين منظور کافيست مقادير متغيرهاي تابع را تغيير داد و مقادير تابع را تا رسـيدن بـه بهـترين حالت مقايسه نمود. البته در اکثر اوقات متغيرهاي تابع تحت تعدادي قيد قرار دارند که از يکسو فضاي جستجو را محدود نموده و از سوي ديگر باعث پيچيده تر شدن مساله مي گردند.
بـنابراين يـک مسـاله بهيـنه سازي از سه جزء مبنايي تشکيل گرديده است (۲۰}: تابع يا توابع مطلوبيت که بايد کميـنه يـا بيشـينه گردند، مجموعه متغيرها در يک دامنه تعريف مشخص و مجموعه قيود اعمال شده به آنها. بسته به نـوع مـتغيرها (حقيقـي ، صـحيح ، مـنطقي ، انتخابي و مجموعه ) و قيود اعمال شده بر آنها (خطي ، غيرخطي و منطقي ) ميـتوان روش مناسـب بـراي حـل مساله بهينه سازي را تعيين نمود(۶}. علاوه بر اين ، مواردي نظير پيوستگي يا عدم پيوسـتگي تـابع مطلوبيت ، بهينه سازي همزمان يک يا چند تابع مطلوبيت ، ، وجود يا عدم وجود مقادير اوليه مناسب ، رفتار تابع نرم يا پيچيده ، وجود يا عدم وجود قيود نيز منجر به انواع مختلفي از مسايل بهينه سازي مي گردند.
چـون در اکـثر مسـايل واقعـي بهينه سازي اوً لا يک جواب تقريبي مناسب در دست نمي باشد و ثانيا تابع بهينه سـازي تغييـرات فـراواني داشـته و داراي بهينه هاي موضعي زيادي است ، نميتوان صرفاً از روشهاي آناليز عددي که درعمـل يکـنوع بهيـنه سازي موضعي (optimization loca١) را انجام مي دهند استفاده نمود چرا که الگوريتم مورد اسـتفاده بايسـتي از بسـتر جـذب ايـن بهينه هاي موضعي عبور نمايد و بهينه سراسري را بدست دهد. لذا استفاده از روشـهاي بهيـنه سـازي موضعي مانند روش نيوتن يا کمترين مربعات حتي با داشتن مقدار اوليه ما را به دام بهينه هاي موضـعي خواهـد انداخـت مگـر اينکه تابع مورد نظر، رفتاري نرم داشته و مقدار اوليه در بستر جذب بهينه سراسري قرار گرفته باشد(۲۱}.
۲-۱- روشهاي بهينه سازي سراسري
روشـهاي متعددي در بهينه سازي سراسري وجود دارد که ميتوان آنها را به سه دسته کلي تقسيم بندي نمود(۴} : روشـهاي iieuristic، روشهاي تقريب (approximation) و روشهاي سيستماتيک (systematic). مثالهايي از هر روش در جدول ۱ ارائه گرديده است .
روشـهاي iieuristic روشـهايي هسـتند کـه زمـان جسـتجوي آنها براي يافتن نقطه بهينه مطلق قابل پيش بيني نيسـت بـا وجود اين در اکثر اوقات بخوبي به جواب مي رسند. اکثر اين روشها تصادفي (stochastic) و بعضي از آنها معين (deterministic) مي باشند. عموماً اگر درمدت زمان طولاني اجرا گردند با احتمال بسيار نزديک به يک ، به نقطه بهيـنه مطـلق مـي رسـند امـا هـنوز نميـتوان گفـت صـد در صـد بـه جـواب رسـيده انـد. سـاده تـرين ايـن روشـها mutipe random start١١ مـي باشـد کـه در آن بهـترين نقطه را از ميان تعدادي نقطه کاملاً اتفاقي بعنوان نقطه شروع يک الگوريتم بهينه سازي موضعي انتخاب کرده و عمل فوق را چندين بار اجرا مي نمايند. درصورتيکه تمامي حالتها
بـه يـک نقطه بهينه موضعي برسد آن نقطه با احتمال بسيار زيادي نقطه بهينه مطلق مي باشد. تکنيکهاي زيادي از قبيل انـتخاب نقاط اتفاقي بصورت هوشمندانه و بهينه سازي موضعي خاص براي سرعت بخشيدن به اين ايده بکار گرفته ميشـوند. اين تکنيکها به سه دسته کلي تقسيم مي شوند که مثالهايي از هر يک در جدول ۲ آمده است . شرح کامل هر يـک از روش هـا در مراجع مربوطه قابل پيگيري مي باشد. در ادامه صرفاً روش الگوريتم ژنتيک تشريح ميگردد که در مساله بهينه سازي طراحي نقاط کنترل مثلث بندي از آن استفاده نموده ايم .
روشـهاي تقـريب روشـهاي هسـتند کـه در آنها تابع مطلوبيت توسط يک تقريبگر مناسب به تابعي ساده تر با بهيـنه هاي موضعي کمتر تبديل ميشود. پاسخ اين مساله ساده تر را مي توان بعنوان يک پاسخ تقريبي براي مساله اصلي درنظر گرفت و با استفاده از يک بهينه ساز موضعي نقطه بهينه مطلق را از اين نقطه رديابي نمود(۳}.
روشـهاي سيسـتماتيک بـه تمامي روشهايي اطلاق ميشوند که توسط روابط رياضي صريح به نقطه بهينه مطلق در يک زمان قابل پيش بيني دست مي يابند. اکثر اين روشها در حالت بدخيم در زمانهاي نمايي ، بسته به ابعاد مساله ، بـه جـواب مـي رسـند کـه عمـلاً در مسايل بزرگ غيرقابل اجرا مي باشند هرچند اطمينان از رسيدن به جواب در آنها صددرصـد است . ساده ترين اين روشها grid search مي باشد که در آن مقدار تابع براي يک شبکه منظم از نقاط در سـطح فضـاي جسـتجو محاسبه شده و بهترين مقدار انتخاب مي گردد. براي دقت هاي بالاتر به شبکه با ابعاد کوچکتر نياز است لذا در عمل اين روش مناسب براي مسايل حداکثر دوبعدي است .
۲-۲- الگوريتم ژنتيک
يکـي از مطرح ترين روش هاي بهينه سازي مورد استفاده در مسائل np-iiard ، الگوريتمهاي تکاملي مي باشند.
در ايـن روش بجـاي جسـتجوي معيـن در فضـاي جسـتجو، از جسـتجوي تصـادفي استفاده مي گردد که يک مدل
محاسباتي مجرد نسبتاً ساده الهام گرفته از طبيعت مي باشد. از بين الگوريتمهاي تکاملي ، الگوريتم هاي ژنتيکي تا کنون مطـرح ترين روش مورد استفاده در اين گروه از روش ها بوده اند. در اين روش جمعيتي از کروموزوم ها با گذر از سه فرآيـند لقـاح ، جهـش و تکـثير از نسـلي به نسل ديگر تکامل مي يابند(۹}. نکته مهم در الگوريتم هاي ژنتيکي تنظيم پارامـترهاي آن اسـت تـا اولا مطـلق بـودن و ثانيـا دقيق بودن نقطه بهينه تضمين شود. از آنجاکه عملگر جهش نقش جسـتجوي سراسـري در فضاي جستجو را دارد هرچه نرخ جهش بيشتر باشد جمعيت نقاط از بستر جذب يک نقطه بهيـنه موضـعي بهـتر درآمـده و تضـمين براي مطلق بودن نقطه بهينه نهايي افزايش مي يابد اما تمرکز حول نقطه بهينه فعـلي کـم شـده و دقـت جسـتجوي نقطـه کـاهش مـي يـابد. از سـوي ديگر عملگر لقاح نقش به اشتراک گذاشتن تجـربه هـاي افـراد مختـلف در فضاي جستجو را ايفا کرده و نهايتاً همه آنها را با هم به سمت نزديکترين نقطه بهينه رهـنمون ميسازد. عملگر انتخاب باعث ميشود نقاط بهتر در جمعيت باقي مانده و در نسلهاي آتي تکثير نمايند با اين اميد که فرزندان آنها نقاط بهتري باشند.
در روش ارائـه شـده در ايـن نوشـته (شکل ۱)، دو تکنيک مکمل براي بهينه سازي طراحي نقاط مثلث بندي بکـار گرفـته شـده اسـت . تکـنيک اول روش mutipe random start١١ بوده که در آن بصورت پياپي جمعيتي نسبتا بـزرگ از نقـاط اتفـاقي در فضـاي جستجو با پراکندگي يکنواخت ايجاد و محاسبه ميشوند. به اين ترتيب ديدي کلي نسـبت بـه رفتار تابع مطلوبيت پيدا شده و بهترين نقطه از بين اين نقاط بعنوان نقطه شروع در مرحله بعد بکار گرفته مـي شـود. در ايـن مـرحله فرض بر اين است که تراکم اين نقاط به حدي است که بهترين نقطه حتماً در بستر جذب نقطه بهينه مطلق قرار گرفته باشد. در مرحله بعد از الگوريتم ژنتيک بعنوان يک بهينه ساز موضعي استفاده شده است .
البته اين روش به تنهايي درصورت تنظيم مناسب پارامترهاي آن به تنهايي قابليت بهينه سازي سراسري را دارد اما در ايـنجا بـه مـنظور هزيـنه محاسباتي کمتر و مشـــکلات موجـــود در تـــنظيم کـــردن انتخاب کاملا اتفاقي ۱۰۰۰ نقطه پارامـترهاي الگوريـتم ژنـتيکي و همچـنين در فضاي جستجوزمانـبر بـودن محاسـبه سرشکني کامل يکانتخاب بهترين ۱۰ نقطه از ميان بـلوک ، از اين تکنيک استفاده شده است . از نقاط موجودآنجا که الگوريتم ژنتيک براي شروع به يک خيرتکامل نقاط توسط الگوريتم جمعيـت اوليـه از نقاط اتفاقي نياز دارد، در شرط ايـنجا نقـاط اتفـاقي در اطراف بهترين نقطه ژنتيک در ۵۰ نسل پايان ؟ حاصـل از مـرحله قـبل تشـکيل ميگـردند.انتخاب اتفاقي ۱۰۰ نقطه درنتيجه چندين بار اجراي اين دو تکنيک اگر اطراف بهترين نقطه موجوديکسـان باشـد بـا احـتمال زياد مبين همان نقطه بهينه مطلق است .
۳- بهينه سازي طراحي نقاط کنترل مثلث بندي هوايي
عمـوم مسـايل طراحي مانند مساله مورد بحث ، از نوع مسايل np-iiard هستند. در اين مسايل با افزايش ابعاد مسـاله ، فضـاي جستجو بصورت نمايي افزايش مي يابد که باعث دشوار شدن حل مساله مي گردد. مساله طراحي نقاط کنـترل مثـلث بـندي نيز يک مساله np-iiard است . براي درک اين موضوع بلوکي را درنظر بگيريد که در آن n نقطه زميـني قـابل تشخيص است . هدف از طراحي انتخاب بعضي از اين نقاط بعنوان نقاط کنترل و تعيين نوع آن ميباشد.
براي هر نقطه چهار وضعيت قابل شناسايي مي توان متصور گرديد: نقطه کنترل سه بعدي ، مسطحاتي ، ارتفاعي يا نقطه بـا مختصـات مجهـول ، کـه در کل n حالت ميشود. حجم اين فضاي جستجو براي طراحي يک بلوک مسطحاتي n اسـت کـه بـاز هـم يـک رابطـه نمايي است . براي درک بيشتر اين فضاي جستجوي حجيم فرض کنيد در يک پروژه فتوگرامـتري معمولي حدود ۱۰۰ نقطه زميني در محاسبات شرکت نمايد. تعداد حالاتي که بايد براي يافتن بهينه ترين نقـاط کنـترل مسـطحاتي تسـت شـود برابـر ۲۱۰۰ بوده که معادل ۱۰۳۰*۱,۲۷حالت ميباشد. بافرض اينکه توسط يک کامپيوتـر بسـيار قوي هر تست ۰,۰۱ ميلي ثانيه بطول انجامد ۱۰۱۷*۴,۱۲ سال بطول خواهد انجاميد تا تمامي حالات تسـت شـده و بهيـنه تـرين طـراحي بدسـت آيد. بهمين منظور بايستي در بهينه سازي از تکنيکهايي استفاده نمود که بصورت هوشمندانه اي فضاي جستجوي فوق را کاهش داده و مستقيماً به اکتشاف نقطه بهينه مطلق بپردازند.
مشـکل دوم غيـر خطـي بـودن مسـاله بهيـنه سازي طراحي نقاط کنترل مثلث بندي است . از آنجاکه برخلاف مسايل خطي هنوز روشي جامع براي حل مسايل غيرخطي پيدا نشده است ، بهينه سازي مساله موردبحث را مشکل تر مـي سـازد. مشکل ديگر وجود نقاط بهينه موضعي مجازي فراوان در تابع مطلوبيت طراحي نقاط کنترل است . بعبارت ديگـر توسـط روشهاي عددي مانند کمترين مربعات نميتوان مساله فوق را حل نمود و بايد تکنيکي بکار گرفته شود کـه بـتواند از دام بهينه هاي موضعي فرار نمايد. براي نمونه قسمتي دوبعدي از فضاي جستجوي مساله موردبحث را در شـکل ۲ نشـان داده ايم که در آن بخوبي بهينه هاي موضعي خود را نشان مي دهند. مساله آخر وجود ناپيوستگي در تـابع مطـلوبيت ميباشد (شکل ۲) که استفاده از روشهاي مبتني بر گراديان را با مشکل مواجه مي سازد. چون الگوريتم ژنتيک صرفا از مقدار تابع و نه مشتق آن استفاده ميکند اين مساله با بکارگيري الگوريتم هاي ژنتيکي مرتفع ميگردد.
