METODE PENCARIAN VARIABEL SEKITAR UNTUK OPTIMISASI KONTINU

METODE PENCARIAN VARIABEL SEKITAR UNTUK OPTIMISASI KONTINU

TESIS

Oleh

NURTAITO SIANTURI 077021067/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

METODE PENCARIAN VARIABEL SEKITAR UNTUK OPTIMISASI KONTINU

TESIS

Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

NURTAITO SIANTURI 077021067/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis

: METODE PENCARIAN VARIABEL SEKITAR UNTUK OPTIMISASI KONTINU Nama Mahasiswa : Nurtaito Sianturi Nomor Pokok : 077021067 Program Studi : Matematika

Menyetujui, Komisi Pembimbing

(Dr. Tulus, M.Si) Ketua

(Dr.Saib Suwilo, M.Sc) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 29 Mei 2009


Telah diuji pada Tanggal: 29 Mei 2009

PANITIA PENGUJI TESIS Ketua

: Dr. Tulus, M.Si

Anggota

: 1. Dr. Saib Suwilo, M.Sc 2. Prof. Dr. Opim Salim Sitompul. MIKom 3. Dra. Mardiningsih, M.Si


ABSTRAK Tesis ini mengajukan suatu pendekatan Heuristik untuk menyelesaikan optimisasi kontinu dengan kendala. Pendekatan ini didasarkan pada versi generalisasi dari metaheuristik pencarian variabel sekitar (VNS). Neighborhood dan distribusi yang berbeda-beda,yang diperoleh dari metrik yang berbeda-beda disusun peringkatnya dan digunakan untuk mendapatkan titik-titik acak dalam tahap penyebaran. VNS juga diajukan untuk menyelesaikan optimisasi dengan kendala. Kendala ditangani dengan menggunakan fungsi penalti titik eksterior di dalam algoritma yang menggabungkan transformasi sekuensial dan penalti eksak. Kata kunci : Optimisasi global, Program non linear, Pencarian variabel sekitar.

i Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

ABSTRACT This thesis addressed a new heuristic approach for solving constrained continuous optimization problems. It is based on a generalized version of the variable neighborhood search metaheuristic. Different neighborhoods and distributions, induced from different metrics are ranked and used to get random points in the shaking step. We also propose VNS for solving constrained optimization problems. The constraints are handled using exterior point penalty functions within an algorithm that combines sequential and exact penalty transformations. Keywords : Global optimization; Nonlinear programming; Variable Neighborhood Search.

ii Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

KATA PENGANTAR

Dengan rendah hati penulis ucapkan segala puji dan syukur kehadirat Tuhan Yang Maha Esa atas berkat rahmat dan ridhoNya penulis dapat menyelesaikan studi Pascasarjana Program Magister Matematika pada Universitas Sumatera Utara hingga pada tahap penyelesaian penyusunan tesis yang berjudul, ”Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu”. Tesis ini merupakan salah satu syarat penyelesaian studi pada Program Studi Magister Matematika SPs Universitas Sumatera Utara. Penulis menyadari bahwa dari awal hingga selesainya penulisan tesis ini, penulis banyak mendapat dukungan dari berbagai pihak, maka pada kesempatan ini penulis mengucapkan terima kasih yang sebesar-besarnya kepada: Bapak Gubernur Sumatera Utara dan Kepala Bappeda Propinsi Sumatera Utara yang telah memberikan beasiswa kepada penulis serta Kepala Dinas Pendidikan Kota Medan yang telah memberikan izin kepada penulis untuk mengikuti perkuliahan di Sekolah Pascasarjana Program Studi Matematika Universitas Sumatera Utara. Bapak Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara yang sudah memberi kesempatan kepada penulis untuk menempuh pendidikan di Universitas Sumatera Utara. Ibu Prof. Dr. Ir. T. Chairun Nisa B., M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang sudah memberi kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. iii Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

Bapak Prof. Dr Herman Mawengkang selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Bapak Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika SPs USU, dan juga sebagai Pembingbing II yang telah memberi bimbingan dan petunjuk kepada penulis sehingga tesis ini dapat terselesaikan. Bapak Dr. Tulus, M.Si selaku Ketua Komisi Pembimbing dan Pembimbing I yang telah banyak memberi bimbingan, saran, dan masukan serta petunjuk penulisan tesis ini sehingga tesis ini dapat diselesaikan.. Seluruh Staf Pengajar pada Program Studi Magister Matematika SPs USU yang telah membekali ilmu pengetahuan kepada penulis selama perkuliahan hingga selesai. Seluruh keluarga, Ayahanda A. Sianturi, Ibunda S. Br. Siburian, Ibu mertua K. Br. Aritonang, Abang dan adik adikku yang senantiasa mendukung dan mendoakan untuk keberhasilan penulis dalam menyelesaikan pendidikan ini. Secara khusus penulis menyampaikan terimakasih dan sayang kepada Ir. Mangatur Sitorus sebagai suami tercinta yang selalu memberikan perhatian, dukungan dan motivasi kepada penulis selama mengikuti pendidikan pada Program Studi Magister Matematika SPs USU. Dan kepada Ananda tersayang Indah Grace Natasya Sitorus dan Jeremi Christian Pasca Sitorus. Rekan-rekan Mahasiswa Program Studi Magister Matematika SPs USU angkatan tahun 2007 yang tak dapat penulis sebutkan satu persatu yang telah banyak membantu penulis dalam perkuliahan maupaun dalam penulisan tesis ini dan tidak lupa penulis ucapkan terimakasih untuk Ibu Misiani, SSi selaku Staf Adiv Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

ministrasi Program Studi Magister Matematika SPs USU yang telah memberikan pelayanan yang baik kepada penulis yang berhubungan dengan administrasi penulis selama mengikuti pendidikan. Keluarga Besar SMA Negeri 8 Medan yang terus mendoakan dan memotivasi penulis selama mengikuti pendidikan di Sekolah Pascasarjana Program Studi Matematika Universitas Sumatera Utara. Semoga tesis ini dapat bermanfaat bagi pembaca dan pihak-pihak yang memerlukannya, namun penulis sadar bahwa sebagai manusia dalam penulisannya tesis ini masih jauh dari sempurna.

Medan,

Mei 2009

Penulis,

Nurtaito Sianturi

v Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

RIWAYAT HIDUP

Nurtaito Sianturi dilahirkan di Tapanuli Utara pada tanggal 30 Maret 1968 dan merupakan anak ketiga dari 7 bersaudara dari Ayah Alfred Sianturi dan Ibu Setia br. Siburian. Pada tahun 1975 penulis pertama sekali mengecap pendidikan pada Sekolah Dasar (SD) Negeri Batubinumbun Muara Tapanuli Utara dan lulus pada 16 Mei tahun 1981, Sekolah Menengah Pertama (SMP) pada SMP Negeri Muara Tapanuli Utara Provinsi Sumatera Utara dan lulus 19 Mei 1984, Sekolah Menengah Atas (SMA) Jurusan Fisika (A1) pada SMA Negeri Muara Kabupaten Tapanuli Utara Provinsi Sumatera Utara dan lulus 2 Juni 1987. Pada tahun 1987 penulis melanjutkan pendidikannya di Universitas Sumatera Utara (USU) Medan pada Fakultas Matematika Dan Ilmu Pengetahuan Alam (FMIPA) Jurusan Matematika D3 dan lulus pada 27 Juli 1990. Pada 1 Januari 1991 diangkat menjadi PNS pada SMA Negeri 1 Dabo Singkep Kepulauan Riau Propinsi Riau sampai tahun 1995.Pada 1 Desember 1995 pindah tugas ke SMA Negeri 8 Medan Propinsi Sumatera Utara sampai sekarang. Agustus 1996 transfer ke Institut Keguruan dan Ilmu Pendidikan ( IKIP ) Medan untuk mengikuti kuliah program S1 dan lulus 3 April 1998. Penulis menikah pada 28 Mei 1999 dan dikaruniai 2 orang anak ( 1 laki-laki dan 1 perempuan ). Pada tahun 2007 penulis mengikuti pendidikan pada Program Studi Magister Matematika SPs USU.

vi Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

ix

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Rumusan Masalah

. . . . . . . . . . . . . . . . . . . .

3

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

3

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

4

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .

4

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

5

BAB 3 METODE PENCARIAN VARIABEL SEKITAR . . . . . . . .

8

3.1 Variable Neighborhood Search (VNS) Dasar . . . . . . . .

11

BAB 4 VNS UNTUK OPTIMISASI KONTINU . . . . . . . . . . . .

16

4.1 VNS umum Kontinu untuk Optimisasi tanpa Kendala . . .

16

vii Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

4.2 VNS Umum Kontinu Titik Eksterior untuk Optimisasi dengan Kendala . . . . . . . . . . . . . . . . . . . . . . . . .

21

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .

25

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

26

viii Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

DAFTAR GAMBAR

Nomor

Judul

Halaman

1.1

Bagan Alir Tahapan Rancangan Penelitian . . . . . . . . . .

4

3.1

Tahap pencarian lokal Heuristik . . . . . . . . . . . . . . .

12

3.2

Tahap dasar VNS . . . . . . . . . . . . . . . . . . . . . .

13

3.3

Tahap dasar VND . . . . . . . . . . . . . . . . . . . . . .

15

4.1

Langkah-langkah dari VNS Umum Kontinu

. . . . . . . . .

19

4.2

Titik eksterior CGVNS . . . . . . . . . . . . . . . . . . .

24

ix Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

BAB 1 PENDAHULUAN

1.1 Latar Belakang Selama beberapa tahun yang lalu, optimisasi dinamis telah menjadi sebuah topik populer dalam penelitian sistem-sistem komputer karena memberikan kesempatan melebihi optimisasi compiler statis melalui kemampuannya untuk mengidentifikasikan hot execution path secara dinamis, sehingga penyesuaian terhadap perubahan perilaku program dan input dan pemberian perbaikan performa bahkan untuk biner disusun dengan optimisasi statis agresif. Banyak sistem optimisasi dinamis memiliki sebuah struktur menyeluruh yang umum, antara lain (i) memilih daerah (fungsi, trace, hyperblock, dan sebagainya) melalui beberapa bentuk profiling dinamis, (ii) menggunakan optimisasi untuk daerah-daerah pilihan, (iii) menyembunyikan versi-versi yang dioptimalkan, dan (iv) mengganti kejadian dinamis yang akan datang dari daerah-daerah awal dengan versi-versi yang dioptimalkan. Persoalan optimisasi global kontinu atau Continuous Global Optimization Problem (CGOP) non linier, secara umum dapat ditulis dalam bentuk: global min f (x) x∈S

(1.1)

Dengan S didefenisikan sebagai berikut: gi (x) ≤ 0,

i = 1, 2, . . . , m

(1.2)

hi (x) = 0,

i = 1, 2, . . . , r

(1.3)

a ≤ x ≤ b,

a, b ∈ Rn

(1.4) 1


2

dimana x ∈ Rn , f : Rn → R, gi : Rn → R, i = 1, 2, . . . , m, hi : Rn → R, i = 1, 2, . . . , r adalah fungsi kontinu non linier. Permasalahan optimisasi global ini secara alami muncul dalam sejumlah aplikasi seperti dalam desain rekayasa lanjutan, analisis data, perencanaan keuangan, manajemen resiko, pemodelan ilmiah dan lain-lain. Sebagian kasus terpenting ditandai oleh optimal lokal untuk menemukan solusi optimal dari usaha pencarian ruang lingkup global yang dibutuhkan. Berdasarkan hasil survei Pardalos dan Romejin (2002), Pardalos dan Rosen (1987), Pinter (1996), Torn dan Zillinskas (1989) ada dua metode untuk menelusuri persoalan optimisasi global kontinu antara lain:

(i) Metode eksak termasuk strategi pencarian numerik (berlaku untuk masalah yang memiliki struktur yang lebih baik seperti program concave). (ii) Metode heuristik tidak memberikan jaminan lokasi untuk optimum global, tetapi memberikan hasil yang memuaskan untuk berbagai masalah optimisasi global. Akhir-akhir ini, apa yang disebut sebagai metaheuristik atau kerangka kerja untuk pembangunan heuristik (dikembangkan untuk memecahkan masalah optimisasi). Banyak penelitian yang telah ada sebelumnya terdiri dari rangkaian solusi acak dan menggunakan pada titik minimasi konvensional dalam berbagai teknik untuk diubah ke dalam minimum lokal. Untuk mencapai probabilitas temuan global minimum sejumlah titik awal harus dilakukan. Strategi ini tentu membutuhkan waktu dan dapat ditelusuri sebagai dimensionalitas peningkatan masalah. Sebahagian dari pendekatan metaheuristik ini menggunakan teknik yang ber-


3

beda untuk menghindari hambatan dalam minimal lokal. Metode dari tipe ini adalah merupakan sebuah simulasi, algoritma genetika, tabu search, variabel search.

Pencarian variabel sekitar atau Variable Neighborhood Search (VNS) adalah salah satu metaheiristik yang dirancang untuk memecahkan masalah optimisasi. Umumnnya VNS berhasil digunakan dalam memecahkan masalah optimisasi. Penulis menyebutkan dua diantaranya yaitu problem pemrograman bilangan bulat campuran dan problem pohon vertex berbobot k-kardinal. Aturan VNS untuk memecahkan masalah optimisasi kontinu murni untuk pertama kalinya dibahas oleh Mladenovic. Dalam tulisan ini dikembangkan heuristik VNS umum untuk menyelesaikan CGOP yang disebut VNS umum kontinu atau Continuous General Variable Neighborhood Search (CGVNS).

1.2 Rumusan Masalah Rumusan masalah dalam peneltian ini adalah bagaimana metode pencarian variabel sekitar untuk optimisasi kontinu.

1.3 Tujuan Penelitian Adapun tujuan penelitian ini adalah menentukan metode pencarian variabel sekitar untuk optimisasi kontinu.


4

1.4 Kontribusi Penelitian Dengan teknik VNS pada optimisasi kontinu dan digunakannya parameterparameter pada VNS diharapkan memberi manfaat pada masa mendatang yang terfokus pada aplikasi continuous general variable neighborhood search (CGVNS) atau pencarian variabel sekitar umum kontinu pada masalah optimisasi global nyata dari industri dan perluasan metode untuk memungkinkan penggantian minimisator lokal selama proses pencarian.

1.5 Metodologi Penelitian Langkah-langkah penelitian ini adalah Menjelaskan optimisasi kontinu, menjelaskan metode VNS, dan menjelaskan VNS untuk optimisasi kontinu serta menarik kesimpulan. Disajikan dalam diagram berikut: Ide Awal VNS untuk optimisasi kontinu ?

Studi literatur ?

Penentuan Rumusan masalah, tujuan dan manfaat penelitian ?

Metode VNS ?

VNS untuk optimisasi kontinu ?

Kesimpulan dan saran Gambar 1.1 : Bagan Alir Tahapan Rancangan Penelitian


BAB 2 TINJAUAN PUSTAKA

Weber multi-sumber adalah masalah optimisasi kontinu pertama yang diajukan untuk diselesaikan dengan VNS dalam Brimberg dan Mladenovic (1996) dan Brimberg et al. (2000). Masalah kontinu lainnya yang ditangani dengan VNS adalah masalah programming bilinier umum (dan kasus khususnya pooling problem, masalah yang umum dari industri minyak). Akan tetapi, walaupun kedua masalah ini didefinisikan dalam variabel kontinu, gerakan dasar ternyata bersifat kombinatorial. Sebagai contoh dalam masalah Weber multi-sumber titik-titik neighborhood (dari penyelesaian kontinu) didefinisikan dengan merelokasi titiktitik fasilitas atau dengan mengalokasikan ulang pelanggan; dengan demikian jumlah penyelesaian neighborhood selalu terhingga. Kaidah-kaidah VNS untuk menyelesaikan masalah optimisasi kontinu ”murni” diajukan pertama kalinya dalam Mladenovic et al. (2003b). Di sana dikemukakan rancangan kode radar polyphase, masalah nonlinier tanpa kendala yang mempunyai fungsi tujuan minimax spesifik. Kemudian dikembangkan paket software GLOB untuk program nonlinier dengan kendala-kotak umum. Untuk fase pencarian lokal VNS dimasukkan beberapa metode programming nonlinier: turun paling tajam, Rosebrock, Nelder-Mead, Fletcher-Reeves, dll. Pengguna menspesifikasi metode apa di antara metode-metode ini yang akan dijalankan. Dalam tahap ini digunakan norma persegi-empat untuk mendefinisikan neighborhood dalam Rn .

Versi lanjutan dari GLOB, untuk menyelesaikan CGOP dengan

kendala-kotak, diajukan dalam Drazic et al. (2006a). Di sana dikemukakan 5 Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

6

beberapa heuristik VNS dasar, yang masing-masing menggunakan fungsi metrik yang berbeda dalam merancang neighborhood untuk tahap demi tahap. Untuk setiap heuristik (metrik) dilaksanakan pencarian dengan kmax (parameter VNS) neighborhood. Pada setiap neighborhood titik tolak acak untuk pencarian lokal ditentukan menurut metrik yang dipilih. Untuk penentuan struktur tigadimensi molekul, yang terbukti merupakan masalah Non Linier Programming (NLP) tanpa kendala dalam Lavor dan Maculan (2004), diamati bahwa distribusi seragam untuk menghasilkan titik-titik secara acak pada tahapan tidak selalu merupakan pilihan terbaik, distribusi yang dirancang khusus memungkinkan dapat memperoleh lebih banyak titik awal untuk turun yang lebih mendekati arah sumbu dan hasil yang jauh lebih baik dalam hal upaya perhitungan. Karena itu, ditambahkan parameter penting lainnya ke VNS kontinu yaitu distribusi probabilitas yang digunakan untuk memperoleh titik acak pada tahap proses. Sepanjang tulisan ini dinotasikan versi VNS yang dipublikasikan terakhir ini sebagai GLOB. Boose (1994) menyebutkan, jika terdapat banyak daerah optimal misalnya sebuah jumlah besar dibandingkan dengan jumlah maksimum pada turunan yang dapat ditunjukkan dalam waktu yang sesuai, maka daerah optimum mungkin menjadi luas dalam suatu nilai dari optimum tak terbatas. Selanjutnya Merle (1999), dalam penulisannya menjelaskan bahwa pada suatu permasalahan dapat digunakan heuristik dalam algoritma eksak. Ini dijelaskan dengan baik bahwa banyak masalah optimisasi kombinatorik seperti pmedian atau masalah sumber-ganda Weber. Selanjutnya Mladenovic dan Hansen (1997), mengatakan VNS merupakan salah satu diantara banyak metaheuristik yang dibentuk untuk menyelesaikan


7

masalah optimisasi. Ini memanfaatkan secara sistematik gagasan daripada perubahan daerah sekitar, keduanya dalam kendala ke daerah minimal dan dihilangkan dari nilai dasar yang terkandung di dalamnya. Kemudian Mladenovic et.al (2007), dalam penelitiannya mengajukan heuristik baru untuk menyelesaikan masalah optimisasi kontinu tanpa kendala. Didasarkan pada versi generalisasi dari metaheuristik VNS, mengajukan VNS untuk menyelesaikan masalah optimisasi dengan kendala. Kendala-kendala ditangani dengan menggunakan fungsi akhir rangkaian dan eksak. Pencarian variable sekitar merupakan suatu gagasan dasar penting dari metaheuristik pada pergantian sistematik sekitar selama masa penentuan dan masa pencarian, berdasarkan pada daerah optimal. Suatu skema dasar dan ekstensi menunjukkan solusi pada masalah yang ada.


BAB 3 METODE PENCARIAN VARIABEL SEKITAR

Heuristik adalah alat penting dalam optimisasi terapan, dan untuk banyak masalah besar dan tidak jarang rumit yang dihadapi di dalam praktek hanya heuristik satu-satunya alat yang bisa diaplikasikan. Tujuan utamanya adalah untuk memberikan, dalam waktu yang layak, penyelesaian mendekati optimal untuk masalah optimisasi dengan kendala atau tanpa kendala. Tambahan lagi, heuristik juga sangat berguna dalam algoritma eksak yang kompleks, untuk mempercepat banyak proses pencarian. Terakhir, heuristik merupakan bahan bangunan penting dalam sistem penemuan pengetahuan berbasis-optimisasi. Masalah optimisasi ada di mana-mana dalam penelitian operasi dan aplikasinya pada banyak bidang. Inteligensi artifisial cenderung lebih terfokus pada masalah pemenuhan kendala. Kemudian heuristik mencapai penyelesaian layak. Kedua jenis masalah tidak begitu berbeda tidak seperti yang mungkin tampak sekilas karena masalah pemenuhan kendala bisa dinyatakan sebagai masalah optimisasi dengan berbagai cara, misalnya sebagai minimisasi jumlah variabel-variabel artifisial yang menyatakan pelanggaran kendala. Kerangka umum untuk heuristik pembangun, yang dikenal sebagai metaheuristik, banyak dikaji dalam dua dekade terakhir. Metaheuristik tersebut meliputi multi-start adaptif (Boese et al, 1994), pencarian kedalaman variabel (Lin dan Kernighan, 1973; Papadimitriou dan Steiglitz, 1982), pencarian genetik (Holland, 1999), simulasi annealing (Kirkpatrick et al., 1983), tabu search (Glover, 1989, 1990, 1995; Glover dan Laguna, 1993, 1997; Hansen dan Jaumard, 1990), 8 Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

9

GRASP (Feo dan Resende, 1995) dan variable neighborhood search (Mladenovic dan Hansen, 1997; Hansen dan Mladenovic, 1998), topik tulisan ini, dan juga beberapa tulisan lainnya ( Reeves, 1993 tentang survei multi-penulis dalam satu buku; Osman dan laporet, 1996 perihal bibliografi yang ekstensif, dan bab lainnya dari buku pegangan ini). Hibrida juga dibahas secara panjang lebar. Walaupun heuristik tradisional, misalnya metode turun sederhana, terkendala dalam optimum lokal pertama yang ditemukan, namun tidak demikian halnya untuk heuristik yang dibangun di dalam paradigma metaheuristik. Semuanya memberikan metode, deterministik atau stokastik, untuk keluar dari optimum lokal yang buruk. Dengan demikian optimum lokal kerapkali berbeda secara berarti dalam nilai dari optimum global, terutama jika terdapat banyak, dampak praktis dari metaheuristik segera tampak. Berbeda dengan keberhasilan ini, teori metaheuristik mengalami ketertinggalan. Walaupun heuristik yang baik kerapkali diperoleh, namun dengan keaslian dan banyaknya penetapan parameter, alasan mengapa heuristik tersebut sebaik kelihatannya sebagian besar tidak diketahui. Dalam hal ini, situasinya bahkan lebih buruk untuk hibrida. Jadi, suatu refleksi atas sifat-sifat yang diinginkan dari metaheuristik, yang akan menjamin kepentingan praktis maupun teoritisnya, pantas untuk dikaji. Adapun sifat-sifat tersebut adalah sebagai berikut:

1. Kesederhanaan. Metaheuristik haruslah didasarkan pada prinsip sederhana dan jelas, yang sebagian besar akan dapat diaplikasikan. 2. Kepaduan. Seluruh tahap heuristik untuk masalah tertentu haruslah secara alamiah berasal dari prinsip metaheuristik.


10

3. Efisiensi. Heuristik untuk masalah tertentu akan memberikan penyelesaian optimal atau hampir-optimal untuk semua, atau setidaknya sebagian besar, kasus realistik. Yang lebih diinginkan, heuristik akan mencari penyelesaian optimal untuk sebagian besar masalah patokan, bilamana ada tersedia. 4. Efektivitas. Heuristik untuk masalah tertentu akan membutuhkan waktu perhitungan moderat untuk memberikan penyelesaian optimal atau mendekati optimal. 5. Kekuatan. Kinerja heuristik haruslah konsisten atas berbagai kasus, yaitu bukan hanya ditajamkan untuk kondisi pelatihan tertentu dan kurang baik untuk lainnya. 6. Ramah-pengguna. Heuristik haruslah terdefinisi dengan jelas, mudah dipahami dan, yang paling penting, mudah digunakan. Ini mengimplikasikan heuristik akan mempunyai sesedikit mungkin parameter dan idealnya tidak ada. 7. Inovasi. Yang lebih diinginkan, prinsip metaheuristik dan/atau efisiensi dan efektivitas heuristik yang dikembangkan darinya akan menghasilkan tipe-tipe aplikasi baru.

Variable neighborhood search adalah suatu metaheuristik baru-baru ini yang berusaha mencapai kualitas-kualitas yang didaftarkan di atas. Ini didasarkan pada prinsip sederhana yang relatif belum dikaji: perubahan sistematik neighborhood selama pencarian. (kaidah-kaidah yang tepat untuk perubahan sedemikian sangatlah penting; beberapa penulis ada kalanya mengajukan untuk mengkombinasikan tipe-tipe gerakan yang berbeda, atau neighborhood, dalam heuristik


11

yang sama, akan tetapi tanpa melakukannya secara sistematik, dan bukan pula merupakan ide utama heuristiknya).

3.1 Variable Neighborhood Search (VNS) Dasar Skema dasar untuk pencarian lokal digambarkan dalam Gambar 3.1. Seperti yang telah dibahas di atas, heuristik ini berhenti segera setelah optimum lokal dicapai. Ini menggunakan satu tipe gerakan atau, padanannya, satu struktur neighborhood. Peningkatan pertama dari skema ini adalah multi-start yaitu: pencarian lokal di-iterasi-kan berkali-kali dari penyelesaian-penyelesaian awal yang dihasilkan secara acak dan penyelesaian terbaik yang diperoleh tetap dipertahankan. Akan tetapi, jika terdapat banyak optimum lokal (yaitu, jumlahnya jauh lebih besar daripada jumlah maksimum turun yang bisa dilaksanakan dalam waktu yang layak) bahkan optimum lokal terbaik ini bisa sangat jauh nilainya dari optimum global [suatu fenomena yang dikenal sebagai bencana Tchebycheff (Boese et al, 1994)]. Yang jelas, multi-start menyebarkan usaha-usahanya, dengan mengeksplorasi banyak lembah tetapi tanpa terfokus pada daerah yang menjanjikan. Hanya inilah tampaknya yang bisa dilakukan jika baik minimum lokal maupun nilainya terdistribusi secara acak dalam ruang penyelesaian. Akan tetapi, sering tidak demikian halnya. Tentu saja, berulang kali diamati bahwa minimum lokal cenderung berkumpul di satu atau beberapa daerah kecil dari ruang penyelesaian ini (seperti yang bisa diperiksa untuk masalah semua optimum lokal mungkin dipero-


12

leh dari syarat orde-satu, misalnya optimisasi kuadratik tanpa kendala dalam 0-1 variabel). Jadi begitu optimum lokal ditemukan pantas kiranya dieksploitasi informasi yang diperoleh dengan cara demikian, yaitu bahwa banyak variabel yang mungkin mempunyai nilai yang sama dengan atau mendekati optimum global (tetapi tetap tidak diketahui). Karena itu, multi-start bisa dimodifikasi untuk mengeksplorasi neighborhood dekat dan kemudian semakin jauh dari penyelesaian yang sedang dipertahankan (atau terbaik yang diketahui) dengan cara probabilistik. Inilah tepatnya yang dilakukan dengan VNS versi dasar, bila menggunakan kumpulan struktur neighborhood paling sederhana, yaitu struktur neighborhood bersarang. Selanjutnya, dipresentasikan formulasi umum dari skema VNS dasar.

Initialization. Select a neighborhood structure N, that will be used in the search; find an initial solution x; Repeat the following until the stopping condition (i.e. finding a local optimum) is met: (a) Find the best neighbor x0 ∈ N(x) of x; (b) If x0 is not better than x, stop. Otherwise, set x = x0 and return to (a);

Gambar 3.1 : Tahap pencarian lokal Heuristik

Nk (k = 1, 2, . . . , kmax ) menotasikan himpunan berhingga dari strukturstruktur neighborhood pra-seleksi, dan Nk (x) menotasikan himpunan penyelesaianpenyelesaian dalam neighborhood ke-k dari x. Tahap-tahap skema VNS dasar dipresentasikan dalam Gambar 3.2.


13

Initialization. Select the set of neighborhood structure Nk , k = 1, . . . , kmax , that will be used in the search; find an initial solution x; choose a stopping condition; Repeat the following until the stopping condition is met: (1) Set k ← 1; (2) Until k = kmax , repeat the following steps; (a) Shaking. Generate a point x0 at random from the k th nieghborhood of x(x0 ∈ Nk (x)); (b) Local search. Apply some local search method with x0 as initial solution; denote with x00 the so obtained local optimum; (c) Move or not. If this local optimum is better than the incumbent, move there (x ← x00) and continue the search with N1(k ← 1); otherwise, set k ← k + 1;

Gambar 3.2 : Tahap dasar VNS

Cara mudah untuk memperoleh himpunan struktur-struktur neighborhood adalah memperhatikan tipe dasar gerakan dan mendefinisikan neighborhood Nk (x) sebagai himpunan penyelesaian-penyelesaian yang diperoleh dengan mengaplikasikan k gerakan sedemikian pada x (tanpa pembalikan). Sebagai contoh misalnya, jika x adalah 0-1 vektor maka gerakan dasar bisa melengkapi suatu komponen. Kemudian neighborhood Nk (x) adalah himpunan vektor-vektor dengan jarak Hamming k dari x. Contoh lainnya muncul untuk traveling salesman problem (TSP) dan masalah routing terkait lainnya. Kemudian tipe gerakan dasar bisa seperti pada heuristik 2-opt (Croes, 1958), yaitu hapus pasangan edge dari tour saat ini dan hubungkan kembali titik-titik ujung dengan satu-satunya cara yang mempertahankan connected tour.


14

Skema Gambar 3.2 didasarkan pada metode pencarian lokal. Salah satunya, pada prinsipnya, dapat digunakan dan perubahan dalam kode untuk mentransformasikan algoritma turun lokal menjadi heuristik VNS kerapkali minimal. Akan tetapi, dapat dilakukan jauh lebih baik dengan menggunakan beberapa neighborhood pada fase turun. Tentu saja, minimum lokal untuk satu neighborhood bisa cepat atau memakan waktu sesuai dengan kesederhanaan gerakan di atas mana itu dibangun dan ukurannya. Ini mengisyaratkan skema variable neighborhood descent (VND) dasar, yang diberikan dalam Gambar 3.3. Heuristik VND bisa dengan mudah dibangun untuk masalah tertentu dengan menggabungkan heuristik-heuristik yang ada dari literatur. Urutan dengan mana heuristik-heuristik tersebut diaplikasikan sangatlah penting dan petunjuk praktis yang baik adalah menyusun peringkatnya menurut ukuran tak-turun dari neighborhood-neighborhood yang digunakannya. Selanjutnya dapat dikaji bahwa: neighborhood-neighborhood yang digunakan dalam suatu heuristik bisa dibagi ke dalam sekumpulan neighborhood bersarang dengan ukuran yang semakin meningkat. Sebagai contoh misalnya, sewaktu mengaplikasikan gerakan 2-opt ke TSP dapat mempertimbangkan l edge terpendek dari masing-masing vertex, kemudian 2l terpendek, dst. untuk suatu parameter l (Hansen et al., 2000a). Juga, jika sebagian neighborhood jauh lebih mudah dieksplorasi daripada neighborhood lainnya, mungkin ada baiknya kembali ke (1), yaitu ke neighborhood pertama segera setelah optimum lokal yang lebih baik ditemukan dengan salah satu neighborhood selanjutnya, ketimbang mengulangi seluruh tahapan dalam rangkaian.


15

0 Initialization. Select the set of neighborhood structures Nk0 , k = 1, . . . , kmax , that will be used in the descent; find an initial solution x; 0 , repeating the following (1) Set k ← 1; (2) Until k = kmax steps:

(a) Exploration of Neighborhood. Find the best neighbor x0 of x(x0 ∈ Nk0 (x)); (b) Move or Not. If the solution thus obtained x0 is better than x, set (x ← x0); otherwise, set k ← k + 1.

Gambar 3.3 : Tahap dasar VND


BAB 4 VNS UNTUK OPTIMISASI KONTINU

4.1 VNS umum Kontinu untuk Optimisasi tanpa Kendala Ide VNS adalah untuk mendefinisikan himpunan struktur-struktur neighborhood Nk , k = 1, . . . , kmax , yang dapat digunakan dengan cara sistematik untuk melakukan pencarian melalui ruang penyelesaian. Sementara dalam pencarian lokal neighborhood tunggal biasanya didefinisikan (kmax = 1), VNS memperluas pencarian dengan radius yang meningkat untuk keluar dari ”permasalahan optimum lokal”. Neighborhood Nk (x) menotasikan himpunan penyelesaian dalam neighborhood ke-k dari x, dan dengan menggunakan metrik ρk , ini didefinisikan sebagai Nk (x) = {y ∈ S|ρk (x, y) ≤ rk }

(4.1)

Nk (x) = {y ∈ S|rk−1 ≤ ρk (x, y) ≤ rk }

(4.2)

atau

di mana rk adalah radius (ukuran) dari Nk (x) yang tidak-turun monoton dengan k. Perhatikan bahwa nilai radius yang sama bisa digunakan dalam beberapa iterasi yang berturutan. Dengan kata lain setiap struktur neighborhood Nk didefinisikan menurut pasangan (ρk , rk ), k = 1, . . . , kmax , dimungkinkan penggunaan metrik yang sama untuk k yang berbeda, misalnya ρ3 bisa sama dengan ρ7 . Pengamatan penting lainnya adalah bahwa walaupun dalam kasus diskrit Nk (x) terhingga, di sini Nk (x) mengandung sejumlah tak hingga titik.

16 Nurtaito Sianturi : Metode Pencarian Variabel Sekitar Untuk Optimisasi Kontinu, 2009

17

Fungsi metrik didefinisikan dengan cara yang biasa, yaitu jarak lp : !1/p n X |xi yi |p (1 ≤ p ≤ ∞) ρk (x, y) = i=1

atau ρk (x, y) = max ?xi − yi ? (p = ∞) 1≤i≤n

Dalam merancang heuristik VNS umum untuk menyelesaikan CGOP harus mempertimbangkan yang hal-hal berikut: (i) Waktu operasi maksimal tmax dibolehkan untuk pencarian. (ii) Jumlah struktur neighborhood kmax digunakan dalam pencarian; (iii) Nilai radius rk , k = 1, . . . , kmax . Nilai ini bisa didefinisikan atau dihitung secara otomatis selama pencarian. (iv) Geometri dari struktur neighborhood Nk , yang didefinisikan dengan pilihan metrik. Pilihan yang biasa adalah l1 , l2 dan l∞ . (v) Distribusi digunakan untuk memperoleh titik acak y dari Nk (x) dalam tahap proses. Distribusi uniform dalam Nk (x) adalah pilihan yang jelas, tetapi distribusi lainnya bisa menghasilkan kinerja yang jauh lebih baik pada sebagian masalah. (vi) Optimisator lokal digunakan dalam tahap pencarian lokal. Biasanya pilihan optimisator lokal tergantung pada sifat-sifat fungsi tujuan. Tersedia banyak algoritma optimisasi lokal untuk fungsi mulus dan fungsi yang tak terdiferensialkan. (vii) Pengurutan neighborhood-neighborhood dan distribusi-distribusi pada tahap proses pencarian.


18

Dalam merancang heuristik VNS dimungkinkan mengurangi jumlah parameter yang harus diberikan. Ini bisa dicapai dengan menetapkan sebagian parameter sebelumnya (misalnya, jumlah titik yang dihasilkan secara acak, geometri, distribusi dan pengurutannya) dan penghitungan nilai radius secara otomatis (misalnya, terdistribusi merata dari 0 hingga diameter himpunan S). Dalam kasus tersebut hanya boleh menspesifikasi tiga parameter: tmax , kmax dan pilihan prosedur pencarian lokal. Algoritma VNS umum yang dipresentasikan di bawah ini memadukan berbagai heuristik berbasis-VNS untuk optimisasi global kontinu tanpa kendala (yaitu, dengan kendala kotak) yang dikembangkan Kovacevic-Vujcic et al. (2004). Seperti yang dinyatakan sebelumnya, dalam penelitian ini disusun daftar heuristik VNS, yang masing-masing menggunakan neighborhood yang diinduksikan dari fungsi metrik tunggal yaitu: heuristik VNS sedemikian diiterasikan hingga syarat berhenti dipenuhi. Di sini digunakan prosedur utama yang sama seperti sebelumnya, tetapi dengan urutan yang berbeda dan dalam satu heuristik yaitu: neighborhoodneighborhood mempunyai jarak yang sama dari incumbent, tetapi yang diinduksikan dari fungsi-fungsi metrik yang berbeda dikaji secara simultan. Dalam implementasi CGVNS digunakan struktur neighborhood yang didefinisikan menurut metrik l1 dan l∞ dan radius yang telah didefinisikan sebelumnya r1 < · · · < rkmax . Pasangan-pasangan (l1 , rk ), (l∞, rk ), k = 1, . . . , kmax menentukan struktur neighborhood menurut (4.1) atau (4.2), di mana ρk sama dengan l1 atau l∞ .


19

Algoritma VNS umum kontinu: /* Initialization*/ 01. Select the set of neighborhood structures Nk , k = 1, . . ., kmax and the array of random ditributions types; 02. Choose an arbitrary initial point x ∈ S 03. Set x∗ ← x, f ∗ ← f (x); 04. Repeat the following steps until the stopping condition is met 05. Set k ← 1 06. Repeat the following steps until k > kmax 07. For all distributions from the array do 08. Generate at random a point y ∈ Nk (x∗) 09. Apply some local search method from y to obtain a local minimum y 0 ; 10. If f (y 0 ) < f ∗ then 11. Set x∗ ← y 0, f ∗ ← f (y 0) and goto line 05; 12. Endif 13. Next 14. Set k ← k + 1; 15. End 16. End 17. Stop Point x∗ is an approximate solution of the problem

Gambar 4.1 : Langkah-langkah dari VNS Umum Kontinu Telah diimplementasikan empat tipe distribusi yang berbeda untuk menghasilkan titik acak dalam tahap proses pencarian. Titik acak diperoleh dengan dua tahap yaitu:

(i) Arah acak d dihasilkan dengan menggunakan salah satu distri busi yang didaftarkan di bawah ini dan setelah itu radius acak r dalam [0, rk ] (atau [rk−1 , rk ]) dengan fungsi kepadatan yang sebanding dengan ukuran bola n-dimensi ditentukan.


20

(ii) Arah d disusun skalanya hingga r dalam metrik yang mendefinisikan geometri dari Nk (x). Jika titik acak yang diperoleh letaknya di luar kendala kotak, titik tersebut dipetakan w.r.t. secara simetri batas ke dalam daerah kotak. Diberikan empat cara yang mungkin untuk menghasilkan titik dari daerah kontinu yaitu: (a) Distribusi D1 : Arah d dihasilkan dengan menggunakan distribusi uniform dalam bola satuan l∞ . (b) Distribusi D2 : Arah d dihasilkan dengan menggunakan distribusi uniform pada bola satuan l1. (c) Distribusi D3 : Arah d dihasilkan dengan menggunakan distribusi yang dirancang khusus pada bola satuan l1 sebagai berikut: (i) Koordinat d1 diambil secara seragam pada [−1, 1], dk diambil secara seragam dari [−Ak , Ak ] dimana Ak = 1 − |d1 | − · · · − |dk−1 |, k = 2, . . . , n − 1 dan dn terakhir mengambil An dengan tanda acak; (ii) koordinat d dipermutasikan secara acak. Fakta bahwa dalam arah acak d sedikit koordinat di berbeda secara berarti dari 0 yang bisa memacu CGVNS secara berarti bila ukuran masalah n besar. (d) Distribusi D4 : Pertama arah d dihasilkan dengan menggunakan distribusi uniform dalam bola satuan l∞ . Kemudian, dengan titik saat ini x dan vektor kendala-kotak a dan b, koordinat di ditentukan skalanya sebagai berikut: (i) jika di ≥ 0 faktor penentuan skala adalah (bi xi)/rkmax (ii) jika di < 0 maka faktor penentuan skala adalah (xi − ai )/rkmax . Dengan demikian, titik selalu berada di dalam batas-batas, Nkmax (x) sama dengan daerah kotak keseluruhan S dan Nk (x) adalah daerah


21

kotak S yang berkontraksi ke arah titik x dengan faktor kontraksi rk /rkmax . Dalam tulisan ini dikemukakan percobaan numerik dengan struktur neighborhood yang didefinisikan menurut pasangan-pasangan (l∞ , r1), . . . , (l∞, rkmax ) dan dengan susunan distribusi (D3 , D2 , D1 , D4 ). Selanjutnya diasumsikan bahwa neighborhood-neighborhood didefinisikan menurut (4.2). Pilihan ini dimotivasi oleh pengalaman perhitungan yang ekstensif. Dengan cara demikian dikurangi jumlah parameter menjadi hanya tiga: kmax , tmax dan pilihan minimisator lokal. Tambahan lagi, untuk memperoleh heuristik yang lebih mudah, dalam versi default (default CGVNS) ditetapkan kmax sama dengan 15.

4.2

VNS Umum Kontinu Titik Eksterior untuk Optimisasi dengan Kendala Metode penalisasi merupakan salah satu pendekatan untuk menentukan

minimum lokal masalah (3.1)-(3.4). Metode ini menyelesaikan masalah optimisasi dengan kendala melalui penyelesaian serangkaian masalah tanpa kendala. Masalah tanpa kendala melibatkan fungsi tambahan yang menyatukan fungsi tujuan bersama-sama dengan suku penalti yang mengukur pelanggaran kendala. Metode penalisasi mencakup dua kelompok utama yaitu: metode penalti titik eksterior, yang menetapkan penalti atas pelanggaran kendala dan metode penalti titik interior, yang menetapkan penalti atas pencapaian batas kendala ketaksamaan. Karena masalah (3.1)-(3.4) mempunyai kendala ketaksamaan dan kesamaan maka lebih umum menyelesaikannya dengan menggunakan metode titik eksterior.


22

Di sini digunakan teknik minimisasi lokal penalti titik eksterior dan mengkombinasikannya dengan strategi VNS untuk mencapai penyelesaian mendekati optimal masalah (3.1)-(3.4). Masalah tanpa kendala yang bersesuaian meminimalkan apa yang disebut dengan fungsi penalti dan mempunyai bentuk: min Fµ q (x) = f(x) +

a≤x≤b

1 Pq (x) µ

(4.3)

dengan penalti Pq (x) =

m X

q

(max{0, g, (x)}) +

i=1

r X

|hi |q

i=1

di mana µ adalah parameter penalti positip dan eksponen penalti q ≥ 1. Jika q = 1 bisa dibuktikan bahwa fungsi penalti adalah eksak, yaitu dari suatu nilai µ yang cukup setiap penyelesaian (lokal) masalah (4.3) adalah minimum lokal dari (3.1)-(3.4). Akan tetapi, fungsi penalti eksak tidak terdiferensialkan di semua titik. Karena alasan tersebut nilai q > 1, yang menjamin keterdiferensialan, juga digunakan. Dalam kasus ini penyelesaian dari (4.3) dengan syarat-syarat ringan konvergen ke minimum lokal dari (3.1)-(3.4) bila µ → 0. Ciri utama dari CGVNS titik eksterior adalah menerapkan metodologi VNS yang dikembangkan pada masalah (4.3) dengan variasi parameter penalti yang tepat. Dengan mengikuti kerangka CGVNS, penyelesaian dasar dari algoritma CGVNS titik eksterior untuk masalah (3.1)-(3.4) dispesifikasi sebagai berikut. Penyelesaian awal x dalam tahap inisialisasi ditentukan sebagai penyelesaian layak dari masalah (4.3) untuk eksponen penalti tetap q dan µ = µ0 , dimana µ0 adalah nilai awal yang diberikan untuk parameter penalti µ. Titik y dalam tahap proses dihasilkan secara acak sebagai penyelesaian layak untuk masalah


23

(4.3) untuk nilai µ saat ini dan kemudian, dalam tahap pencarian lokal, metode pencarian lokal diaplikasikan untuk menentukan minimum lokal y 0 dari masalah ini. Jika y 0 lebih baik daripada x w.r.t. fungsi Fµq , algoritma bergerak ke y 0 dan kontinu dengan µ yang sama. Dalam hal lainnya, algoritma tetap di x dan nilai µ mungkin berkurang. Yaitu, jika µ lebih besar daripada nilai minimal tertentu µmin , µ diperoleh dengan mengalikannya dengan faktor konstanta α, 0 < α < 1, dan fungsi penalti diubah dengan tepat. Jika tidak lebih besar dari faktor toleransi layak yang sangat kecil ε, titik dianggap layak untuk masalah (3.1)-(3.4) dan bukti titik terbaik sedemikian tetap bertahan. CGVNS titik eksterior menggunakan parameter tambahan yang biasa untuk metode fungsi penalti yaitu:

(i) q - eksponen fungsi penalti; (ii) α ∈ (0, 1) - laju penurunan penalti; (iii) ε - bilangan kecil, yaitu toleransi untuk pemeriksaan kelayakan; (iv) µ0 dan µmin - nilai awal dan nilai minimal dari parameter penalti.

Dalam tulisan ini, dikemukakan percobaan numerik yang diperoleh dengan q = 2, α = 0, 9, ε = 10−10 , µ0 = 1 dan µmin = 10−8 . Sebagian besar nilai parameter yang diajukan diperoleh sebagai hasil dari analisa perhitungan yang ekstensif. Sebagai contoh, nilai faktor penalti q = 2 diberikan setelah mengoperasikan metode atas serangkaian kasus test dengan q = 1, 1, 1, . . . 1, 9, 2.


24

Algoritma CGVNS titik eksterior: /* Initialization*/ 01. Select the set of neighborhood structures Nk , k = 1, . . . , kmax, the penalty function parameters (q, µ0, µmin ) and the array of random distributions types; 02. Choose an arbitrary initial point x feasible for the box constrained problem (7) 03. Set x∗ ← x, f ∗ ← fµ,q (x), fF∗ ← ∞, µ ← µ0 ; 04. Repeat the following steps until the stopping condition is met 05. Set k ← 1 06. Repeat the following steps until k > kmax 07. For all distributions from the array do 08. Generate at random a point y ∈ Nk (x∗ ) 09. Apply some local search method from y to obtain a local minimum y0 ; 10. If Pµ,q (y0 ) ≤ ε and f(y0 ) then set x∗ ← y0 , fF∗ ← f(y0 ) 11. If Fµ,q (y0 ) < Fµ,q (x∗ ) then 12. Set x∗ ← y0 , fF∗ ← f(y0 ) and goto line 05 13. Else 14. Set µ ← max{µmin , αµ}; 15. Endif 16. Next 17. Set k ← k + 1 18. End 19. End 20. If fF∗ = ∞ (i.e., x∗F is not found) then 21.

The feasible solution x∗F is obtained by local minimize applied to Fµ,q (x) with q = 1, µ = µmin starting from x∗

22. Endif 23. Stop. Point x∗F is an approximate feasible solution of the problem.

Gambar 4.2 : Titik eksterior CGVNS


BAB 5 KESIMPULAN

Dalam tulisan ini di ajukan heuristik baru untuk menyelesaikan masalah optimisasi kontinu (tanpa kendala dan dengan kendala). Ini didasarkan pada metaheuristik pencarian neighborhood variabel dan disebut VNS umum kontinu (CGVNS). CGVNS diselesaikan dengan menggunakan metode titik eksterior karena mempunyai kendala ketaksamaan dan kesamaan. Ide pengubahan neighborhood dalam pencarian dieksplorasi sepenuhnya. Struktur neighborhood dalam Rn disimpulkan dari fungsi metrik yang berbeda-beda. Beberapa titik dari neighborhood yang sama dipilih secara acak menurut distribusi yang berbeda-beda dan digunakan beberapa minimisator lokal.


DAFTAR PUSTAKA

Audet,C.,Brimberg,J., Hansen, P., Le Digabel, S.,Mladenovic, N.,(2004). Pooling problem: Alternate formulations and solution methods. Management Science 50 (6 ),761-776 Avriel, M., (1976 ). Non Linier Programming: Analisys and Methods. PrenticeHall,Englewood Cliffs, NJ Brimberg, J., Mladenovic, N., (1996 ). A Variable Neighborhood Algorihtm for Solving the Continuous Location-Allocation Problem. Studies in Location Analisys 10, 1-12 Cvijovic, D., Klinowski, J., (1995 ). Tabo Search: An approach to the multiple minima problem. Science 667,664-666. Drazic, M., Kovacevic-Vujcic, Mladenovic, N., ( 2006 a ) . GLOB Anew VNS-based software for global optimization. In: Liberty, L., Maculan, N. (Eds), Global Optimization: From Theory to Implementation, Nonconvex Optimization and its Application Series, Vol. 84. Springer, Berlin, pp. 135-154. Drazic, M., Lavour, C., Maculan, N., (2006b ). A Continuous Variable Neighborhood Search Heuristic for Finding the three dimensional structure of a molecul. European J. Oper. Res., doi:10.1016/j. Ejor.2006.06.052. Du Merle, O. D. Villenevue, J. Desrosier & P. Hansen. (1999). Stabilized Column Generation. Discrete Math. 229-237 F, Glover. & G. Kochenberger. (2003). Handbook of Metaheuristic. Kluwer, Boston. F. Glover, M, Laguna. (1993). Modern Heuristic Techniques for Combinatorial Optimization. Blackwell, Oxford. Hansen, P & Mladenovic, N. (2001). Variable Neighborhood Search : Principles and Application, Europen J. Oper. Res.. 449-467. Hansen, P., Mladenovic, N.,(2003 ). Variable Neighborhood Search. In: Glover, F., Kochenberger, G. (Eds), Handbook of Metaheuristics. Kluwer, Dordrecht, pp. 145-184. Kovacevic-Vujcic, V., Cangalovic, M., Drazic, M., Mladenovic, N., (2004 ). VNSbased heuristics for Contnuous Global Optimization. In: Le thi Hoai An, Pham Dinh Thao (Eds.),Modelling ,Computation and Optimization in Information System and Management Sciences. Hermes Science Publishing,pp. 215-222. K. D. Boese, A. B. Kahng, S. Muddu. (1994). A new Adaptive multi-Start Technique for Combinatorial Global Optimization. Oper. Res. Lett. 16; 101-113


27

Lavor, C., Maculan, N., ( 2004 ). A function to test methods applied to global minization of potential energi of molecules. Numerical Algorithms 35, 287300. Mladenovic, N., Hansen, P.,(1997). Variable Neighborhood Search. Comput. Oper. Res. 24. 1097-1100. Mladenovic, N.(1995). Variable Neighborhood Algorithm : A NewMetaheuristic for Combinatorial Optimization. Montreal. Pardalos, P. M., Rosen, J.B., (1987) Constrained Global Optimization: Algorithms and Applications. Springer,Berlin. Pinter, J.D., (1996). Continuous Global Optimization Software: A brief review. Optima 52, 1-8. Pardalos, P.M.,Romejin, H, E. (Eds.). 2002. Handbook of Global Optimization. Kluwer, Dortrecht Torn, A., Zilinskas, A., (1989). Global Optimization. Springer,Berlin.


METODE PENCARIAN VARIABEL SEKITAR UNTUK OPTIMISASI KONTINU

Recommend Documents