PENDEKATAN MAKSIMASI DIVERSITAS UNTUK OPTIMASI TUJUAN GANDA (MULTI-OBJECTIVE)

PENDEKATAN MAKSIMASI DIVERSITAS UNTUK OPTIMASI TUJUAN GANDA (MULTI-OBJECTIVE)

TESIS

Oleh DASWATI SIGALINGGING 077021052/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

PENDEKATAN MAKSIMASI DIVERSITAS UNTUK OPTIMASI TUJUAN GANDA (MULTI-OBJECTIVE)

TESIS

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

Oleh DASWATI SIGALINGGING 077021052/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis

: PENDEKATAN MAKSIMASI DIVERSITAS UNTUK OPTIMISASI TUJUAN GANDA (MULTI-OBJECTIVE) Nama Mahasiswa : Daswati Sigalingging Nomor Pokok : 077021052 Program Studi : Matematika

Menyetujui, Komisi Pembimbing

(Prof. Dr. Opim Salim Sitompul, MSc) 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

: Prof. Dr. Opim Salim Sitompul, M.Sc

Anggota

: 1. Dr. Saib Suwilo, M.Sc 2. Dr. Sutarman, M.Sc 3. Drs. Sawaluddin, MIT


ABSTRAK Salah satu pendekatan paling umum untuk optimisasi tujuan ganda adalah membangkitkan batas efisien keseluruhan atau parsial dan kemudian memutuskan tentang penyelesaian yang diinginkan dalam proses pengambilan-keputusan tingkat yang lebih tinggi. Dalam tesis ini, dikembangkan metode baru untuk menghasilkan batas yang efisien untuk masalah tujuan ganda, yang disebut pendekatan maksimisasi diversitas (Diversity Maximazing Approach = DMA). Pendekatan ini dapat menyelesaikan masalah mixed-integer dan kombinatorial. DMA menentukan penyelesaian optimal Pareto dengan memaksimalkan ukuran dan menjamin pembentukan himpunan lengkap titik-tik efesien. Penyelesaian ini didefinisikan sebagai penyelesaian paling beraneka ragam yang bertujuan memaksimalkan jarak antara titik efisien baru dan titik terdekat dalam himpunan bagian batas efisien tertentu. Ukuran keanekaragaman menjamin bahwa di setiap tahap prosedur, batas efisien parsial terdiversifikasi dengan baik. Batas efisien parsial ini bisa dipersepsikan sebagai himpunan tersaring dari batas efisien total dan bisa digunakan oleh pengambil keputusan dalam kasus batas efisien total memuat terlalu banyak titik. Kata kunci: Riset Operasi, Optimasi Tujuan Ganda, Pendekatan Maksimasi Diversitas

i Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

ABSTRACT One of the most common approaches for multiobjective optimization is to generate the whole or partial efficient frontier and then decide about the preferred solution in a higher-level decision-making process. In this paper, a new method called the Diversity Maximizing a proposed diversity measure and guarantees generating the complete set of efficient points. This solution is defined as the most diverse solution. In fact, it aims to maximize the distance between the new efficient point and the closest point in the given subset of the efficient frontier. The diversity measure assures that in every stage of the procedure, the partial efficient frontier is well diversified. This partial efficient frontier can be perceived as a filtered set of the complete efficient frontier and can be used by the decision maker in case the complete efficient frontier contains too many points. Keyword: Operation Research, Multiobjective optimization,Diversity Maxi mization Approach.

ii Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

KATA PENGANTAR Puji syukur penulis mengucapkan kepada Sang Maha Pencipta yang telah memberikan begitu banyak nikmat, sehingga tesis ini dapat terselesaikan dengan baik. Dalam menyelesaikan pendidikan di Sekolah Pascasarjana Universitas Sumatera Utara ini, penulis banyak mendapatkan dukungan dari berbagai pihak, maka pada kesempatan ini penulis mengucapkan terima kasih dan penghargaan yang sebesar-besarnya kepada :

1. Prof. dr. Chairuddin P. Lubis, DTM&H, Sp. A(K), selaku Rektor Universitas Sumatera Utara. 2. Prof. Dr. Ir. T. Chairun Nisa. B, M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. 3. Drs. Salmi Effendi, M.Pd, selaku Kepala Sekolah SMA Negeri 8 Medan yang telah memberikan dukungan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara ini. 4. Prof. Dr. Herman Mawengkang, selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara, yang banyak memberikan bimbingan dan motivasi kepada penulis sehingga pendidikan ini dapat terselesaikan dengan baik. 5. Dr. Saib Suwilo, MSc, selaku Sekretaris Program Studi Magister Matematika dan Dosen Pembimbing II yang telah memberikan bimbingan dan iii Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

petunjuk sehingga tesis ini dapat terselesaikan dengan baik. 6. Prof. Dr. Opim Salim Sitompul, M.Sc, selaku Dosen pembimbing I yang telah memberikan bimbingan dan petunjuk sehingga tesis ini dapat terselesaikan dengan baik. 7. Seluruh Staf Pengajar pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara, yang telah memberikan ilmu pengetahuan kepada penulis selama perkuliahan hingga selesai. 8. Secara khusus penulis menyampaikan terima kasih yang tak terhingga kepada Ayahanda tercinta Lomse Sigalingging dan Ibunda tercinta (Alm) Timoria Marpaung, yang doa-doanya selalu menyertai penulis. Kepada suami tercinta Drs. Adian Sinaga dan ananda tercinta Roni J. H. Sinaga yang selalu menjadi motivator penulis. 9. Kepada semua pihak yang telah turut membantu baik langsung maupun tidak langsung yang penulis dapatkan selama ini.

Semoga tesis ini bermanfaat bagi pembaca dan pihak-pihak yang membutuhkannya.

Medan, Penulis,

Daswati Sigalingging

iv Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

RIWAYAT HIDUP Daswati Sigalingging dilahirkan di Sait Uruk pada tanggal 8 Desember 1965 dan merupakan anak ketiga dari delapan bersaudara dari Ayah Lomse Sigalingging dan Ibu (Alm) Timoria Marpaung. Menamatkan Sekolah Dasar Negeri 122396 Pematang Siantar pada tahun 1977, Sekolah Menengah Pertama pada SMP Negeri 5 Pematang Siantar pada tahun 1981, Sekolah Menengah Atas pada SMA Swasta HKBP Pematang Siantar pada tahun 1984. Pada tahun 1985 memasuki Perguruan Tinggi D3 FKIP Nommensen Pematang Siantar dan memperoleh gelar pada tahun 1988. Pada tahun 1989 diangkat sebagai Calon Pegawai Negeri Sipil di SMA Negeri Parsoburan Kecamatan Parsoburan. Pada tahun 1992 menikah dengan Drs. Adian Sinaga dan dikaruniai 1 putra Roni J. H. Sinaga. Pada tahun 1993 mutasi ke SMA Negeri 3 Binjai, pada tahun 1996 mengikuti kuliah S1 di IKIP Medan dan memperoleh gelar Sarjana Pendidikan (SPd) pada tahun 1997. pada tahun 2001 mutasi ke SMA Negeri 8 Medan sampai sekarang. Pada tahun 2007 mengikuti program studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara.

v Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

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

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

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

iii

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

v

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

vi

DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

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

ix

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

1

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

1

1.2 Rumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

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

4

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

4

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

4

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

6

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.1 Optimasi Tujuan Ganda (Multi-Objective) . . . . . . . . . . . . . .

9

3.2 Pendekatan Maksimasi Diversitas (Keanekaragaman) . . . . . .

15

3.2.1 Ukuran Diversitas (Keanekaragaman) . . . . . . . . . . . .

17

vi Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

3.2.2 Teorema Utama . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

BAB 4 PENDEKATAN MAKSIMASI DIVERSITAS UNTUK OPTIMASI TUJUAN GANDA (MULTI-OBJECTIVE) . . . . . . . . . . . . . . . .

25

4.1 Algoritma Pendekatan Maksimasi Diversitas (DMA) . . . . . .

25

4.1.1 Formulasi Pemrograman Bilangan Cacah (Divercity Maximization Approach-DMA) . . . . . . . . . . . . . . . . . . . .

25

4.1.2 Algoritma M-DMA . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.1.3 Contoh Masalah Penjadwalan dalam Optimasi Tujuan Ganda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

4.2 Formulasi Pemrograman Cabang dan Batas (Branch-and-Bound B&B) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . . . . . . . . . .

43

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

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

45

vii Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

DAFTAR TABEL

Nomor

4.1

Judul

Halaman

Input data dari contoh permasalahan penjadwalan dalam optimasi tujuan ganda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

4.2

Titik titik efisiensi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.3

Contoh Kasus Penerapan Algoritma B-DMA . . . . . . . . . . . . . .

40

viii Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

DAFTAR GAMBAR

Nomor

Judul

Halaman

1.1

Bagan Alir Metodologi Penelitian . . . . . . . . . . . . . . . . . . . . .

5

3.1

Contoh dari Perbatasan Efisiensi . . . . . . . . . . . . . . . . . . . . . .

18

3.2

Contoh dari Situasi Pertalian dalam α . . . . . . . . . . . . . . . . . .

23

4.1

Pengembangan perbatasan efisiensi dari contoh kasus dengan menggunakan M-DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2

34

Pengembangan Perbatasan Efisiensi dari Contoh Kasus dengan Menggunakan B-DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

42

BAB 1 PENDAHULUAN

1.1 Latar Belakang Perkembangan peradaban yang semakin kompleks dalam era globalisasi ini bukan hanya membawa manusia pada kesejahteraan yang semakin tinggi, akan tetapi juga menimbulkan sisi-sisi gelap dan disparitas pendapatan yang semakin mengkhawatirkan. Karena diidentikan sebagai abad penguasaan manajemen berbasis ilmu pengetahuan (knowledge management dan scientific management), maka para pemenang persaingan adalah pihak-pihak yang mampu memanfaatkan ilmu pengetahuan semaksimal mungkin. Salah satu ilmu terapan praktis yang selalu diperlukan, khususnya yang berhubungan dengan pendekatan kuantitatif dalam penyelesaian suatu permasalahan yang semakin kompleks, adalah Riset Operasi (operation research). Kebanyakan dari permasalahan praktis tersebut melibatkan optimasi tujuan ganda (multi-objective), contohnya dalam hal perencanaan dan peramalan pasar maka manajemen perusahaan akan menentukan produk yang dapat diserap (atau digemari) konsumen dengan melakukan survei pasar, yang selanjutnya menugaskan unit (divisi) produksi untuk memproduksi barang tersebut semaksimal mungkin sekaligus meminimumkan biaya produksi dari batasan-batasan yang ada. Cara yang paling umum untuk memecahkan persoalan tujuan ganda adalah melakukan pembobotan (dengan skala prioritas) dari objektifitas berbeda tersebut, dan kemudian mengembangkan suatu metoda yang efisien untuk memecahkan permasalahan dengan tujuan (objektif) tunggal. Masalah utama dengan pen1 Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

2 dekatan ini adalah menemukan skala prioritas yang utama dan ini sering sekali tidak bisa diamati secara langsung, contohnya biaya kerugian dikarenakan penurunan reputasi yang disebabkan oleh banyak faktor, yang menyimpang dari suatu lingkungan dengan lingkungan yang lain. Sebagai tambahan, model aditif ini mengasumsikan suatu hubungan linier diantara sasaran-sasaran yang ingin dicapai. Pada sisi lain, seorang perancang sistem (pengambil keputusan) dapat memilih solusi yang lebih baik dari yang diberikan (sejumlah kecil) alternatif-alternatif dibandingkan menghimpun bobot untuk sasaran hasil. Dalam satu kasus pendekatan perbatasan efisiensi yang sedemikian adalah pantas, perancang sistem perlu mempertimbangkan hanya efisiensi, yaitu bukan dikuasai, konfigurasi reka bentuk pada perbatasan efisiensi. Bagaimanapun, menemukan satu perbatasan efisiensi adalah permasalahan sulit. Perbatasan efisiensi yang dihasilkan mungkin sewaktu-waktu berisi terlalu banyak solusi-solusi, lebih dari perancang sistem yang mampu tangani dalam proses pengambilan keputusan. Suatu pendekatan untuk menyelesaikan masalah perbatasan efisiensi disebut pendekatan maksimasi diversitas (Diversity Maximization Approach - DMA), yang berkorespondensi dengan pembatasan-pembatasan pendekatan yang ada. Pendekatan yang paling umum untuk pemeliharaan diversitas adalah menerapkan suatu penalti untuk individu yang menyokong ketidakcukupan untuk diversitas (Holland, 1975; Goldberg dan Richardson, 1987). Ini dapat dipandang sebagai satu usaha untuk mengkombinasikan dua fungsi tujuan (objektif), terpisah ke dalam nilai skalar tunggal. Bagaimanapun, pembobotan linier dari dua fungsi tujuan (objektif) adalah tidak harus sesuai dan sukar untuk mengendalikannya


3 (Soule, 1998). Dalam optimasi tujuan ganda (multi-objective), diversitas digunakan dengan mengkombinasikannya dengan tujuan (objektif) ganda lain (De Jong, Watson, dan Pollack, 2001; De Jong dan Pollack, 2003; Toffolo dan Benini, 2003). Hasil-hasil dengan penggandaan fungsi tujuan (objektif) yang lain menyatakan bahwa pendekatan untuk pemeliharaan diversitas adalah sangat berpeluang. Pendekatan maksimasi diversitas dapat diterapkan untuk berbagai permasalahan tujuan ganda dengan sembarang jenis fungsi objektif dan algoritmaalgoritma yang diturunkan dari DMA, untuk memperoleh solusi efisien dari semua bagian-bagian perbatasan efisiensi, sedemikian hingga semua perbatasan efisiensi parsial mempunyai solusi-solusi paling berbeda dari perbatasan efisiensi utuh. Beberapa algoritma berbasiskan DMA yang diturunkan, diuji dan yang menarik ditemukan untuk optimisasi tujuan ganda. Untuk itu dalam penulisan tesis ini, penulis tertarik menguraikan pendekatan maksimasi diversitas untuk optimasi tujuan ganda (multi-objective).

1.2 Rumusan Masalah Cara yang paling umum untuk memecahkan persoalan tujuan ganda (multiobjective) adalah melakukan pembobotan (dengan skala prioritas) dari objektifitas berbeda tersebut, dan kemudian mengembangkan suatu metoda yang efisien untuk memecahkan permasalahan dengan tujuan (objektif) tunggal. Masalah utama dengan pendekatan ini adalah menemukan skala prioritas yang utama dan ini sering sekali tidak bisa diamati secara langsung. Suatu pendekatan untuk menyelesaikan permasalahan tujuan (objektif) ganda dengan sembarang jenis fungsi


4 objektif adalah dengan pendekatan maksimasi diversitas (Diversity Maximization Approach - DMA). Sehingga bagaimanakah menyelesaikan perma-salahan tujuan ganda dengan pendekatan maksimasi diversitas (Diversity Maximization Approach - DMA).

1.3 Tujuan Penelitian Tujuan penelitian ini adalah menyelesaikan permasalahan tujuan (objektif) ganda dengan pendekatan maksimasi diversitas (Diversity Maximization Approach - DMA), sehingga solusi optimum dapat tercapai.

1.4 Kontribusi Penelitian Penelitian ini diharapkan dapat memberikan sumbangan dalam bidang matematika secara umum dan khususnya dalam bidang matematika terapan sehingga dapat membantu perancang sistem (decision maker) menemukan penyelesaian permasalahan optimasi tujuan ganda (multi-objective).

1.5 Metodologi Penelitian Penelitian ini bersifat literatur dan dilakukan dengan mengumpulkan informasi dari referensi beberapa buku, jurnal ilmiah dan makalah yang menimbulkan gagasan dan mendasari penelitian yang dilakukan. Adapun langkah-langkah yang dilakukan dalam penelitian ini mengikuti bagan alir dibawah ini, yakni :


5

Gambar 1.1 Bagan Alir Metodologi Penelitian


BAB 2 TINJAUAN PUSTAKA

Cohon (1985) membedakan antara metode pembentukan dan metode berbasis - preferensi untuk penanganan optimisasi tujuan ganda (multi-objective). Ehrgott dan Gandibleux (2002) membedakan antara ”mode a priori”, di mana semua preferensi pengambilkeputusan diketahui di awal proses pengambilan keputusan dan ”mode a posteriori”, di mana suatu himpunan penyelesaian-penyelesaian optimal Pareto dihasilkan dan kemudian dianalisa oleh pengambilkeputusan. Banyak pendekatan yang ada untuk menghasilkan penyelesaian optimal Pareto terfokus pada masalah kontinu dan sangat efisien bila himpunan layak dalam ruang tujuan konveks. Metode paling umum dan mungkin paling tua adalah metode pembobotan yang telah disebutkan, misalnya dalam Chankong dan Haimes (1983). Metode ini baik untuk penentuan batas efisien di mana ruang tujuan adalah konveks. Metode p-power berbobot dan metode minimaks berbobot adalah merupakan versi peningkatan dari metode pembobotan untuk menangani masalah non-konveks. Das dan Dennis (1998) serta Mesac dan Mattson (2002) menunjukkan peningkatan untuk metode pembobotan terhadap distribusi penyelesaian optimal Pareto yang diperoleh. Steuer (1986) mempresentasikan dan membahas banyak metode yang ada untuk menghasilkan batas efisien. Karena alasan praktis, dimungkinkan mencari himpunan bagian dari batas efisien total dan bukan himpunan secara keseluruhan. Dalam kasus ini, tak satupun pendekatan ini bisa menjamin bahwa batas efisien parsial terdiri dari titik-titik efisien beraneka ragam atau terdistribusi de6 Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

7 ngan baik. Dengan menggunakan metode pembobotan, misalnya, dan dengan menetapkan nilai-nilai yang terdistribusi merata untuk bobot, tidak selamanya menghasilkan himpunan titik-titik efisien yang terdistribusi dengan baik. Pemeliharaan diversitas merupakan yang terpenting untuk pengembangan dan aplikasi dari metoda-metoda perhitungan evolusioner dan estimasi dari algoritma - algoritma distribusi fungsi tujuan (Yuan dan Gallagher, 2005). Pendekatan yang paling umum untuk pemeliharaan diversitas adalah menerapkan suatu penalti untuk individu yang menyokong ketidakcukupan untuk diversitas (Holland, 1975; Goldberg dan Richardson, 1987). Ini dapat dipandang sebagai satu usaha untuk mengkombinasikan dua fungsi tujuan (objektif), terpisah ke dalam nilai skalar tunggal. Bagaimanapun, pembobotan linier dari dua fungsi tujuan (objektif) adalah tidak harus sesuai dan sukar untuk mengendalikannya (Soule, 1998). Dalam optimasi tujuan ganda (multi-objective), diversitas digunakan dengan mengkombinasikannya dengan tujuan (objektif) ganda lain (De Jong, Watson dan Pollack, 2001; De Jong dan Pollack, 2003; Toffolo dan Benini, 2003). Dalam hal ini, diusulkan untuk menggunakan tujuan (objektif) diversitas dengan mengkombinasikannya terhadap tujuan (objektif) tunggal yang lain, yakni fungsi normal. Hasil-hasil dengan penggandaan fungsi tujuan (objektif) yang lain menyatakan bahwa pendekatan untuk pemeliharaan diversitas adalah sangat berpeluang. Metode pemeliharaan diversitas untuk optimasi multi-objective adalah paling efektif untuk memelihara diversitas dan menentukan solusi terbaik. Dapat disimpulkan bahwa diversitas pemeliharaan multi-objective adalah satu metoda pemeliharaan diversitas efektif dan efisien yang ditemukan untuk aplikasi


8 umum dalam algoritma-algoritma genetik. Metode pemeliharaan diversitas multiobjective tidak hanya mencari titik-titik solusi di bawah atau atas puncak-puncak kecocokan lokal, tetapi juga memelihara individu yang berbeda dari populasi yang mungkin. Sebagai hasilnya, diversitas genetika adalah tinggi, dan secara relatif bagian terbesar dari ruang pencarian yang meliputinya (Snijders, Paul, et.al; 2006) . Masin M dan Bukchin J, (2006) mengungkapkan bahwa pendekatan maksimasi diversitas (Diversity Maximization Approach - DMA) didasarkan pada dalil berikut. Diberikan himpunan X dari penyelesaian layak dan suatu fungsi objektif f : X → Rk . Tanpa kehilangan keumumannya, misalkan bahwa nilai-nilai dari semua sasaran hasil harus diperkecil. Misalkan EF dinotasikan perbatasan efisien dalam X. Diberikan E himpunan bagian dari EF , dan misalkan α(x) terdefinisi untuksetiap x ∈ X, sebagai berikut :

fi (x) α(x) = max min e∈E 1≤i≤K fi (e)


BAB 3 LANDASAN TEORI

3.1 Optimasi Tujuan Ganda (Multi-Objective) Banyak permasalahan praktis melibatkan optimisasi tujuan ganda. Dalam perencanaan dan pengendalian produksi, yang bertujuan meminimalkan keterlambatan, lama aliran produk, kapasitas yang dibutuhkan, dan lain-lain. Dalam sistem jasa, seseorang mungkin memaksimalkan tingkat jasa sambil meminimalkan biaya operasi. Dalam masalah rantai penyediaan, biaya persediaan dan pemesanan kembali biasanya diminimalkan. Dalam manajemen proyek, durasi proyek dan sumberdaya yang dibutuhkan diminimalkan sambil memaksimalkan ukuran kualitas. Dalam masalah rancangan tata ruang, permasalahannya mungkin meminimalkan aliran bahan sambil memaksimalkan nilai kedekatan yang terkait dengan ukuran non-kuantitatip. Dalam semua masalah ini, dan banyak lagi masalah lainnya, ada perimbangan sampai tingkat tertentu antara tujuan-tujuan yang berbeda (atau ukuran-ukuran kinerja) dan penentuan penyelesaian terbaik sangat sulit. Cara yang umum untuk menyelesaikan masalah tujuan ganda adalah menetapkan bobot untuk tujuan-tujuan yang berbeda sesuai dengan arti relatip pentingnya, dan kemudian mengembangkan metode yang tepat untuk menyelesaikan masalah tujuan tunggal (single-objective) yang diperoleh. Masalah utama dengan pendekatan ini adalah menentukan bobot yang tepat, dimana bobot kerapkali tidak dapat diamati secara langsung (misalnya, biaya yang timbul akibat dari reputasi yang hilang) dan dipengaruhi oleh banyak faktor, yang berbeda antara satu lingkungan dengan lingkungan lainnya. Selain itu, fungsi tujuan berbobot 9 Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

10 biasanya mengasumsikan hubungan linier antara tujuan-tujuan, yang tidak selamanya bersesuaian dengan preferensi yang sesungguhnya dari pengambil keputusan. Pendekatan lain adalah memberikan kepada pengambil keputusan himpunan (relatip kecil) dari penyelesaian-penyelesaian atau alternatip ”yang layak”, dan membiarkannya memilih penyelesaian yang diinginkan dari himpunan tertentu. Himpunan penyelesaian-penyelesaian ”yang layak” biasanya terkait dengan himpunan penyelesaian optimal Pareto, dimana tidak mungkin meningkatkan suatu tujuan tanpa memperburuk tujuan lainnya. Bayangan dari himpunan penyelesaian - penyelesaian optimal Pareto dalam ruang tujuan disebut batas efisien (atau takdidominasi). Pengambil keputusan diharapkan memilih titik yang diinginkan dari batas efisien, yang didasrkan pada pertimbangan tambahan. Saat ini ada dua masalah yang terkait dengan pendekatan ini. Masalah pertama berkenaan dengan kesulitan dalam membentuk batas efisien (sekalipun masalah tujuan tunggal hasil dekomposisi relatip mudah diselesaikan). Satu pendekatan adalah mengubah fungsi tujuan ganda menjadi tujuan tunggal, misalnya, sebagai jumlah berbobot dari tujuan-tujuan. Akibatnya, masalah diselesaikan berulang kali dengan nilai bobot yang berubah dan atau batasan tambahan. Masalah kedua terkait dengan jumlah titik pada batas efisien. Jumlah ini mungkin ada kalanya terlalu besar; jauh lebih besar dari apa yang dapat ditangani pengambil keputusan dalam proses pengambilan keputusan. Dalam kasus ini, perancang akan tertarik pada sebagian yang relatip kecil dari batas efisien untuk pemilihan penyelesaian yang diinginkan. Namun demikian, himpunan parsial akan merupakan semua perimbangan dari batas efisien secara


11 keseluruhan. Untuk ini biasanya diaplikasikan pendekatan penyaringan dan proses keseluruhan dalam pembentukan batas efisien total dan kemudian mengeliminir bagianbagian yang signifikan darinya, yang tampak tidak efisien. Catat bahwa dalam banyak kasus, tahap pertama dalam pembentukan batas efisien total bisa jadi tidak mungkin karena himpunan mungkin terlalu besar atau bahkan takberhingga. Cohon (1985) membedakan antara metode pembentukan dan metode berbasis - preferensi untuk penanganan optimisasi tujuan ganda. Pada bagian yang disebutkan pertama, tidak ada pengetahuan apriori tentang relatip pentingnya tujuan dipertimbangkan dan kepada pengambil keputusan diberikan sedikit penyelesaian optimal Pareto dan kemudian penyelesaian yang diinginkan dipilih dari himpunan ini. Pada bagian yang disebut terakhir, preferensi yang diketahui tentang masing-masing tujuan digunakan untuk proses optimisasi. Sama halnya, Ehrgott dan Gandibleux (2002) membedakan antara ”mode a priori”, di mana semua preferensi pengambil keputusan diketahui di awal proses pengambilan keputusan dan ”mode a posteriori”, di mana suatu himpunan penyelesaian optimal Pareto dihasilkan dan kemudian dianalisa oleh pengambil keputusan. Mereka juga menyebut ”mode interaktif”, di mana preferensi dimasukkan oleh pengambil keputusan selama proses penyelesaian melalui tahap-tahap dialog. Proses ini bisa dipandang sebagai penentuan interaktif suatu kompromi yang memuaskan untuk pengambil keputusan. Metode interaktif sudah di luar ruang lingkup tulisan ini. Banyak pendekatan yang ada untuk menghasilkan penyelesaian optimal Pareto terfokus pada masalah kontinu dan sangat efisien bila himpunan layak dalam


12 ruang tujuan konveks. Metode paling umum dan mungkin paling tua adalah metode pembobotan yang telah disebutkan, misalnya dalam Chankong dan Haimes (1983). Metode ini baik untuk penentuan batas efisien di mana ruang tujuan adalah konveks. Metode perpangkatan-p berbobot dan metode minimaks berbobot adalah merupakan versi peningkatan dari metode pembobotan untuk menangani masalah nonkonveks. Das dan Dennis (1998) dan Mesac dan Mattson (2002) menunjukkan peningkatan untuk metode pembobotan terhadap distribusi penyelesaian optimal Pareto yang diperoleh. Yang disebut pertama mengisyaratkan metode irisan batas normal untuk memperoleh penyelesaian optimal Pareto terdistribusi merata. Akan tetapi, metode ini juga menghasilkan titik-titik nonefisien dan mengabaikan beberapa titik efisien bila jumlah tujuan lebih besar dari dua. Yang disebut terakhir ini mengisyaratkan penggunaan pemrograman fisika bersama-sama dengan Pseudopreferensi tujuan untuk memperoleh titik-titik efisien berdistribusi-merata. Metode batasan-ε adalah pendekatan lain yang didasarkan pada mempertahankan salah satu tujuan dan membatasi tujuan lainnya di dalam nilai yang dispesifikasi-pengguna. Steuer (1986) mempresentasikan dan membahas banyak metode yang ada untuk menghasilkan batas efisien. Karena alasan praktis, kita mungkin mencari himpunan bagian dari batas efisien total dan bukan himpunan secara keseluruhan. Dalam kasus ini, tak satupun pendekatan ini bisa menjamin bahwa batas efisien parsial terdiri dari titik-titik efisien beraneka ragam atau terdistribusi dengan baik. Dengan menggunakan metode pembobotan, misalnya, dan dengan menetapkan nilai-nilai yang terdistribusi merata untuk bobot, tidak selamanya menghasilkan himpunan titik-titik efisien yang terdistribusi dengan baik.


13 Karena itu, pada umumnya, masalah tujuan ganda cenderung lebih kompleks daripada masalah tujuan tunggal, terutama bila masalah kombinatorial terlibat, biasanya diaplikasikan heuristik untuk menghasilkan penyelesaian optimal Pareto. Pendekatan paling umum didasarkan pada algoritma genetik. Algoritma genetik bisa efektif terlepas dari sifat dari fungsi tujuan dan batasan. Selain itu, ketimbang menentukan penyelesaian satu per satu, seperti yang dilakukan banyak algoritma lainnya, algoritma ini menahan suatu populasi penyelesaian yang terus meningkat sesuai dengan jumlah iterasi. Algoritma genetik pada awalnya dikembangkan untuk optimisasi tujuan-tunggal. Karenanya, algoritma ini bisa diaplikasikan secara langsung untuk menyelesaikan masalah tujuan ganda yang diubah menjadi masalah tujuan tunggal. Dengan menggunakan algoritma genetik untuk menghasilkan penyelesaian optimal Pareto lebih kompleks, dan fungsi kecocokan harus dimodifikasi sesuai dengan hal ini. Satu cara untuk melakukannya adalah membagi populasi secara keseluruhan ke dalam himpunan bagian dan menggunakan nilai kecocokan tujuan yang berbeda untuk masing-masing himpunan bagian. Anggota-anggota dari masing-masing sub-populasi yang akan ditransfer ke generasi berikutnya dipilih melalui kaidah stokastik. Kemudian, semua himpunan bagian digabungkan menjadi populasi baru dan iterasi baru dimulai. Yun et al. (2001) mengajukan peningkatan di atas dengan menggunakan analisa pembungkusan data (DEA) untuk batas efisien berbentuk konveks dan dengan menggabungkan analisa pembungkusan data menyeluruh (GDEA) dan algoritma genetik untuk menghasilkan batas efisien dalam masalah tujuan ganda umum. Dengan menggunakan algoritma genetik untuk optimisasi multi-tujuan dibahas secara panjang lebar dalam Deb (2001).


14 Algoritma genetik adalah heuristik dengan sifat stokastik, hanya aproksimasi batas efisien yang bisa diperoleh. Yang jelas karena masing-masing penyelesaian yang diperoleh hanya potensial efisien, jumlah titik efisien juga diaproksimasi. Karena alasan tersebut, ada penelitian yang terfokus pada menghasilkan himpunan penyelesaian-penyelesaian yang terdistribusi dengan baik yang bisa diasumsikan merupakan himpunan representatif dari batas efisien riil. Zitzler dan Thiele (1999) mengembangkan Algoritma Evolusioner Pareto Kekuatan (SPEA), yang mengisyaratkan distribusi yang relatip baik dari penyelesaian-penyelesaian optimal Pareto dibandingkan dengan empat algoritma evolusioner (EA) tujuan ganda lainnya. Osyczka dan Krenich (2001) menggunakan pendekatan penyaringan dalam EA yang didasarkan pada penghapusan penyelesaian-penyelesaian yang berdekatan satu sama lain dalam ruang tujuan. Untuk mengendalikan penyelesaian metode penyaringan, mereka mendefinisikan metode interval yang tidak dapat dibedakan dengan jelas. Deb et al. (2003) mengajukan algoritma evolusioner tujuan ganda (MOEA) keadaan-mantap mendominasi-ε, yang mencapai distribusi yang baik dari titik-titik efisien potensial dengan relatip cepat. Gunawan et al. (2003) mempresentasikan algoritma genetik tujuan ganda (MOGA), yang melanggengkan keanekaragaman titik-titik efisien dengan memaksimalkan metrik entropy. Sebuah survei komprehensif tentang optimisasi kombinatorial tujuan ganda bisa ditinjau dalam Ehrgott dan Gandilbleux (2000, 2002), yang membahas metode eksak dan metode aproksimasi dan juga berbagai masalah kombinatorial.


15 3.2 Pendekatan Maksimasi Diversitas (Keanekaragaman) Diketahui himpunan bagian batas efisien, Pendekatan Maksimasi Diversitas (DMA) bertujuan menentukan titik efisien berikutnya yang menghasilkan himpunan bagian baru yang lebih berenaka ragam. Ternyata, DMA memaksimalkan jarak antara titik baru dan titik terdekat dalam himpunan bagian batas efisien yang diberikan. Penyelesaian baru ini didefinisikan sebagai penyelesaian paling beraneka ragam. Misalkan untuk permasalahan minimisasi vektor tujuan ganda, diberikan sebagai berikut : [P 0]

min y = (f (1)(x), f (2)(x), . . . , f (K) (x))

(3.1)

dengan batasan x ∈ X

(3.2)

di mana X ⊂ Rn adalah himpunan penyelesaian layak, Y ⊂ RK adalah bayangannya dalam ruang tujuan, dan f : X → RK adalah fungsi tujuan yang memproyeksikan X ke Y . Jika x ∈ X, maka y = f (x) ∈ Y dan nilai tujuan ke-i dari penyelesaian x adalah y (i) = f (i) (x). Dengan mengasumsikan bahwa himpunan X adalah kompak dan masing-masing fungsi tujuan f kontinu dan positip. Untuk x1 , x2 ∈ X, y1 = f(x1 ), y2 = f (x2 ) ∈ Y , misalkan y1 = y2 dan y1 ≤ y2 (i)

(i)

(i)

(i)

jika masing-masing y1 = y2 dan y1 ≤ y2 untuk semua i. Dua penyelesaian x1 , x2 ∈ X, y1 = f(x1), y2 = f(x2 ) ∈ Y ekuivalen jika y1 = y2. (i)

(i)

(i)

Untuk jika y1 < y2 jika y1 ≤ y2 untuk semua i dan y1

(i)

< y2 untuk

sebagian i. Dalam kasus ini, akan dikatakan bahwa y2 didominasi oleh y1 , atau y1 mendominasi y2. Misalkan XPar menotasikan himpunan total penyelesaianpenyelesaian optimal Pareto dalam X, yaitu penyelesaian x ∈ XPar jika dan


16 hanya jika tidak ada x1 ∈ X, sedemikian sehingga f(x1 ) < f (x). Jika penyelesaian x adalah optimal Pareto, maka kita sebut y = f (x) efisien. Himpunan total titik-titik efisien dalam ruang tujuan Yeff disebut batas efisien. Pengambil keputusan biasanya tertarik dalam menentukan Yeff dan bukan XPar . Dalam hal ini himpunan XPar bisa memuat penyelesaian-penyelesaian ekuivalen; yaitu, penyelesaian-penyelesaian yang berbeda dengan nilai tujuan yang sama, sementara dalam ruang tujuan himpunan Yeff memuat tepat satu titik untuk masingmasing vektor nilai tujuan. Jumlah titik dalam himpunan Yeff bisa bertumbuh secara eksponensial dalam ukuran masalah. Ada dua alternatip umum untuk menjadikan himpunan polinominal dalam ukuran masalah. Himpunan Aε didefinisikan sebagai aproksimasi - ε dari Yeff bila setiap titik di dalam Aε tidak bisa didominasi suatu titik lainnya dengan rasio lebih besar dari 1 + ε, yaitu tidak terdapat y1 ∈ Y sedemikian se(i)

hingga untuk semua y ∈ Aε , y (i) > (1 + ε)y1 untuk sebagian tujuan i = 1, . . . , K. Papadimitirou dan Yannakakis (2000) menunjukkan bahwa jika fungsi-fungsi tujuan dibatasi, terdapat Aε yang terdiri dari sejumlah titik yang polinomial dalam ukuran masalah dan 1/ε dan eksponensial dalam jumlah tujuan. Pilihan lainnya adalah menyaring batas efisien Yeff . Misalkan Ri adalah rentang nilai-nilai yang mungkin dari tujuan i atas batas efisien, Ri = maxy∈Y (y (i)) − miny∈Y (y (i)). Himpunan Fε didefinisikan sebagai batas efisiensi disaring-ε bila masing-masing rentang Ri dibagi dengan d1/εe segmen yang sama, 0 < ε < 1, dan dari masingmasing hiper-persegi dimensi-K paling banyak pada satu titik efisien dipilih. Dengan kata lain, tidak terdapat y1 ∈ Y sedemikian sehingga, untuk semua (i)

y ∈ Fε , y (i) > y1 + εRi untuk sebagian tujuan i = 1, . . . , K. Tidak sulit dilihat bahwa jika semua Ri , i = 1, . . . , K, dibatasi, maka terdapat Fε yang terdiri


17 dari sejumlah titik yang tidak tergantung pada ukuran masalah, polinomial dalam 1/ε dan eksponensial dalam jumlah tujuan.

3.2.1 Ukuran Diversitas (Keanekaragaman) Diketahui himpunan bagian E dari Y dan titik y ∈ Y , misalkan ukuran diversitas αE (y) didefinisikan sebagai berikut: (i)

αE (y) =

max ye ∈E

max 1
y (i) − ye ∆ie

!

(3.3)

di mana 4iε adalah koefisien penentuan skala positip. Dikatakan E sebagai batas efisien parsial jika E ⊂ Yeff. Bila himpunan E jelas, maka digunakan notasi α(y) sebagai pengganti αE (y). Untuk x ∈ X, untuk penyederhanaan, dapat digunakan αE (x) sebagai pengganti αE (f (x)). Persamaan (3.3) dapat dijelaskan sebagai berikut. Pertama, dalam hal fungsi ”min” dalam, akan dibandingkan titik layak y dengan masing-masing titik efisien yε ∈ E. Untuk setiap titik y, dengan menentukan ukuran kinerja paling (i)

diinginkan i ukuran untuk mana (y (i)yε /4iε sekecil mungkin (dan negatip jika (i)

y (i) < yε . Maka, dapat ditentukan titik yang ”terdekat” ke titik y dari antara semua yε ∈ E (fungsi ”max” luar). Lemma 1. Diberikan suatu himpunan bagian E dari Y dan titik y ∈ Y , misalkan (i)

αE (y) = maxyε ∈E (min1≤i≤K (y (i)yε /4iε ). Maka,

(1) jika αE (y) > 0, maka y didominasi oleh yε ∈ E, (2) jika αE (y) < 0, maka y tidak didominasi oleh suatu titik yε ∈ E, (i)

(3) jika αE (y) = 0, maka yε ≤ y untuk yε ∈ E dan yε = y ((i) untuk suatu i,


18 (4) jika αE (y) < αE (y1 ) untuk y1 ∈ Y , maka y tidak didominasi oleh y1, (5) jika E1 ⊆ E2 ⊂ Y , maka αE1(y) ≤ αE2(y) untuk setiap y ∈ Y .

Bukti. Sifat-sifat berasal secara langsung dari definisi dari αE (y). Catat bahwa αE (y) = 0 berarti bahwa terdapat yε ∈ E, yang ekuivalen dengan atau mendominasi y. Contoh kecil berikut menggambarkan dasar pemikiran di balik ukuran diversitas yang diajukan. Untuk penyederhanaan, diasumsikan bahwa semua koefisien penentuan skala sama dengan satu. Misalkan Y = {ya, yb , y1, y2 , y3} adalah ruang tujuan layak, E = {ya , yb} adalah batas efisien parsial, yang diperlihatkan dalam Gambar 3.1. Pertama, akan ditunjukkan bahwa nilai negatip dari α(y) hanya diperoleh untuk titik yang tidak didominasi yε ∈ E. Maka, nilai dari uku (1) (1) (2) (2) . Karena ran diversitas untuk y1 adalah α(y1 ) = max min y1 ya , y1 yb (2) (2)

y1 ya

(1) (1)

< 0 dan y1 yb

< 0, maka α(y1 ) < 0. Di lain pihak, jika diperhatikan

Gambar 3.1 Contoh dari Perbatasan Efisiensi (1) (1) (2) (2) (1) (1) (2) (2) y2 maka diperoleh α(y2 ) = max min y2 ya , y2 ya , min y2 yb , y2 yb .


19 (1) (1)

(2) (2)

Karena ya mendominasi y2 , maka y2 ya > 0 dan y2 yb > 0, yang menghasilkan α(y2 ) > 0. Selanjutnya, akan ditunjukkan prinsip diversitas. Menurut prinsip ini, penyelesaian yang paling beranekaragam adalah penyelesaian dengan jarak terbesar dari penyelesaian terdekat dengannya pada batas efisien. Titik paling beranekaragam y ∈ Y diidentifikasi dengan mempunyai nilai terkecil α(y). Dalam menghitung nilai α(y) untuk y1 dan y2 , dapat dilihat seperti cara (2) (2) (1) (1) di atas, α(y1 ) = max y1 ya , y1 yb , yaitu jarak antara y1 dan titik terdekat dengannya pada batas efisien (catat bahwa karena kedua nilai negatip, maka maksimum akan ditentukan oleh bentuk negatip terkecil atau dengan jarak terkecil). Serupa halnya, dapat dilihat bahwa nilai dari α(y3 ) adalah α(y3) = (2) (2) (1) (1) max y3 ya , y3 yb . Karena diasumsikan bahwa faktor penentuan skala sama (2) (2)

(2) (2)

dengan 1, maka dapat dilihat bahwa α(y1 ) = y1 ya dan α(y3) = y3 ya . Akibatnya, karena ya lebih dekat dengan y3 daripada dengan y1 (berkenaan dengan tujuan 2 dalam kasus ini), α(y1 ) < α(y3). Dengan demikian, y1 didefinisikan sebagai titik yang lebih beranekaragam daripada y3 . Koefisien penentuan skala 4iε dibutuhkan untuk menormalisasikan semua fungsi tujuan untuk perbandingan yang lebih baik sewaktu menghitung ukuran diversitas. Bila tertarik dalam menghasilkan Yeff, setiap koefisien penentuan-skala positip baik. Akan tetapi, jika tertarik pada himpunan bagian ”paling representatip” dari batas efisien, maka penentuan skala tujuan berarti untuk memperoleh ”representatip” dari seluruh bagian batas efisien. Berikut beberapa contoh koefisien penentuan skala 4iε yang mungkin :

(1) 4iε = Ri untuk semua i dan ε - rentang nilai yang mungkin dari tujuan i atas batas efisien, Ri = maxy∈Yeff (y (i)) − miny∈Ytextef f (y (i)). Bila nilai ri


20 berikutnya tidak diketahui, maka itu bisa ditaksir dengan menggunakan rentang ukuran kinerja i dalam E ⊆ Yeff, batas efisien parsial: (i) fˆmax =

î = R

max (ye(i) ),

(i) fˆmin =

min (ye(i))

(3.4)

  (i) (i) (i) (i)  fˆmax − fˆmin , jika fˆmax − fˆmin > 0

(3.5)

ye ∈ E

 

1

ye ∈ E

, untuk yang lainnya

(i) (i) ˆ i ≤ Ri . Catat bahwa jika fˆmax − fˆmin > 0, maka R (i)

(2) 4iε = ye untuk semua i dan e nilai tujuan i dari ye ∈ R. (i)

(3) 4iε = fmin untuk semua i dan e nilai terbaik (”optimal”) untuk fungsi (i)

tujuan i, fmin = miny∈Y (y (i)).

3.2.2 Teorema Utama ∗ = arg miny∈Y (y (i)) adalah Menurut definisi ukuran diversitas, α(y), yoptimal

titik paling beraneka ragam (penyelesaian paling beraneka ragam dalam ruang keputusan yang bersesuaian) sebagaimana telah didefinisikan sebelumnya. Dalam bagian ini, diberikan syarat-syarat untuk pemasukan penyelesaian paling beranekaragam dalam batas efisien dan untuk penentuan batas efisien secara keseluruhan. Lemma 2. Misalkan E ⊆ Yeff dan arg miny∈Y α(y). Maka (1) jika α(y ∗) < 0 dan y ∗ tidak didominasi dalam Y/E, maka y ∗ ∈ Yeff. (2) jika α(y ∗) = 0, maka Yeff = E, (3) jika −ε ≤ α(y ∗ ), maka :


21 (i)

(a) jika 4ie = ye

untuk semua i dan e, maka Aε ∈ E, di mana ε =

ε/(1 − ε), ˆ i untuk i dan e dan maxy∈Y (y (i)) − miny∈Y (y (i) > 0 (b) jika 4eε = R eff efft untuk semua i, maka Fε ⊆ E.

Bukti. Catat bahwa α(y) = 0 untuk setiap y ∈ E; karena itu α(y ∗) ≤ 0.

(1) Dari Lemma 1, y ∗ tidak didominasi oleh suatu titik di dalam E. Karena y ∗ tidak didominasi dalam y\E, maka y ∗ merupakan bagian dari batas efisien. (2) Dari Lemma 1, jika α(y ∗ ) = 0, maka setiap titik di dalam Y ekuivalen dengan atau didominasi oleh suatu yε ∈ E. Karena itu, ditemukan himpunan Yeff . (i)

(3) (a) Jika 4ie = ye untuk semua i dan e dan −ε ≤ α(y ∗), maka −ε ≤ (i)

(i)

miny∈Y (maxyε ∈E (min1≤i≤K ((y (i)yε )/yε ))) atau 1 ≤ miny∈Y (maxyε ∈E (i)

(i)

(min1≤i≤K ((1/(1 − ε))(yε /yε )))). Karena itu, tidak ada y ∈ Y sede(i)

mikian sehingga untuk semua yε ∈ E, yε > 1/(1 − ε)y (i) untuk suatu i. Jika ε = ε/(1 − ε), maka (1 + ε) = 1/(1 − ε) dan, akibatnya, tidak (i)

ada y ∈ Y sedemikian sehingga untuk semua yε ∈ E, yε > (1 + ε)y (i) untuk suatu i. ˆ i untuk semua i dan e dan −ε ≤ α(y ∗ ), maka −ε ≤ (b) Jika 4iε = R (i)

ˆ i ))). Sama halnya dengan baminy∈Y (maxyε ∈E (min1≤i≤K ((y (i)yε )/R gian (3.a) tidak ada y ∈ Y sedemikian sehingga untuk semua yε ∈ (i) ˆ i untuk suatu i. Catat bahwa jika maxy∈E (yε(i)) − E, yε > y (i) + εR (i) î ≤ R ˆ i untuk semua i. Karena itu, tidak ada miny∈E (yε ) > 0, maka R


22 (i)

y ∈ Y sedemikian sehingga untuk semua yε ∈ E, yε > y (i) + εRi untuk suatu i.

Bagian (1) memberikan syarat untuk penambahan y ∗ pada batas efisien. Bagian (2) menunjukkan syarat untuk penentuan batas efisien keseluruhan. Bagian (3a) dan (3b) mempresentasikan masing-masing syarat untuk penentuan aproksimasi - ε dan batas efisien disaring-ε. Catat bahwa syarat kedua atas y ∗ pada bagian (1) diperlukan karena y ∗ dapat didominasi oleh titik lain dalam Y \E walaupun α(y ∗) < 0. Ini ditunjukkan oleh contoh berikut yang digambarkan dalam Gambar 2. Misalkan E = {yε } dan semua koefisien penentuan skala sama dengan satu. Maka, α(y1 ) dan α(y2) dihitung sebagai berikut: (1) (1)

(2) (2)

(2) (2)

(1)

α(y1 ) = min(y1 yε > 0, y1 yε < 0) = y1 yε < 0 dan α(y2 ) = min(y2 yε(1) > (2) (2)

(2) (2)

0, y2 yε < 0) = y2 yε < 0. (2)

(2)

Karena y1 = y2 , maka α(y1 ) = α(y2) < 0. Sekalipun ukuran keanekaragaman kedua titik identik, namun jelas bahwa y2 didominasi oleh y1 dan karenanya tidak boleh termasuk dalam batas efisien. Misalkan y3 adalah titik layak, di mana (1) (1)

α(y3 ) = y3 yε dan α(y1) = α(y2 ) = α(y3 ) = B. Dapat dilihat bahwa semua titik pada garis tebal yang lewat melalui y1 , y2 dan y3 dalam Gambar 3.2 akan mem(2)

punyai nilai yang sama α(y) = B. Nilai ini ditentukan oleh y (2)yε

= B pada

(1)

garis horizontal dan y (1)yε = B pada garis vertikal. Catat bahwa yε tetap efisien (1)

(2)

hanya bila y (1) > yε untuk semua titik layak pada garis horizontal dan y (2) > yε

untuk semua titik layak pada garis vertikal. Lemma 3 menunjukkan bagaimana dapat menjamin bahwa y ∗ ∈ arg miny∈Y α(y) tidak didominasi di dalam Y \E. K P ∗ (i) , di mana Lemma 3. Misalkan E ⊆ Yeff dan y = lex miny∈Y α(y), wi y i=1

wi > 0 untuk semua i. Maka,


23

Gambar 3.2 Contoh dari Situasi Pertalian dalam α (1) y ∗ ∈ arg miny∈Y α(y), dan (2) y ∗ tidak didominasi di dalam Y .

Bukti.

(1) Trivial dari rumus y ∗. (2) Dari bagian 1, α(y ∗) ≤ α(y) untuk semua y ∈ Y . Dari Lemma 1, jika α(y ∗ ) < α(y), maka y ∗ tidak didominasi oleh y. Jika α(y ∗) = α(y), maka K P wi y (i), menjamin bahwa y ∗ bagian kedua dari minimum leksikografik, i=1

tidak didominasi y.

Sekarang dapat dinyatakan teorema utama untuk penentuan batas efisien total atau parsial dalam ruang tujuan.


24

∗

Teorema 1. Misalkan E ⊆ Yeff dan y = lex miny∈Y

K P (i) α(y), wi y , di mana i=1

wi > 0 untuk semua i. Maka,

(1) jika α(y ∗) < 0, maka y ∗ ∈ Yeff, (2) jika α(y ∗) = 0, maka Yeff = E, (3) jika −ε ≤ α(y ∗ ), maka : (i)

(a) jika 4ie = ye

untuk semua i dan e, maka Aε ∈ E, di mana ε =

ε/(1 − ε), ˆ i untuk i dan e serta maxy∈Y (y (i)) − miny∈Y (y (i)) > 0 (b) jika 4iε = R eff eff untuk semua i, maka Fε ⊆ E.

Bukti. Semua hasil merupakan akibat langsung dari Lemma 1 sampai dengan Lemma 3.


BAB 4 PENDEKATAN MAKSIMASI DIVERSITAS UNTUK OPTIMASI TUJUAN GANDA (MULTI-OBJECTIVE)

4.1 Algoritma Pendekatan Maksimasi Diversitas (DMA) Pada bagian ini, dipresentasikan dua algoritma berbasis-DMA untuk menentukan penyelesaian optimal Pareto dalam optimisasi tujuan ganda. Prosedur pertama didasarkan pada penyelesaian versi modifikasi dari formulasi masalah awal secara berulang-ulang, dan algoritma kedua, dimasukkan prinsip DMA dalam pendekatan cabang dan batas.

4.1.1 Formulasi Pemrograman Bilangan Cacah (Divercity Maximization Approach-DMA) Berdasarkan pendekatan maksimasi diversitas (DMA), dikembangkan algoritma iteratif yang dimulai dengan himpunan kosong E dan membentuk batas efisien dengan menambahkan satu titik per iterasi. Algoritma berakhir bila dihasilkan batas efisien secara keseluruhan atau bila diberikan ε, ditemukan Aε , atau Fε. Masalah P1 berikut digunakan untuk menentukan titik awal ye ∈ E: K X

wi f (i) (x)

(4.1)

dengan kendala x ∈ X

(4.2)

[P1] Min Z =

i=1

di mana wi , i = 1, . . . , K adalah bobot positip murni, yaitu wi = 1 untuk semua i = 1, . . . , K. Diberikan himpunan bagian E dari Yeff, masalah P2 didefinisikan sebagai 25 Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

26 berikut: [P2] Min Z = lex min α,

K X

!

wi f (i) − (x)

i=1 (i)

f (i) (x) − ye dengan kendala α = max min 16i6K Ye ∈E ∆ie

!

x∈X

(4.3) (4.4) (4.5)

Karena masalah P2 adalah replika eksak dari masalah optimisasi yang digunakan dalam Teorema 1 (Bab 3), maka ini memungkinkan untuk menentukan penyelesaian optimal Pareto atau menunjukkan bahwa Yeff = E. Persamaan Nonlinier (4.4) dapat dilinierisasikan dengan menggunakan variabel biner sebagai berikut: [P3] Min Z = lex min α,

K X

wi f (i) (x)

!

(4.6)

i=1

dengan kendala α ≥ βe

∀ye ∈ E

(4.7)

(i)

βe 6

f (i) (x) − ye ∀i = 1, . . . , K, ye ∈ E ∆ie K (i) X γ2ie − ye γ 1ie βe = ∀ye ∈ E ∆ ie i=1 K X

(4.8) (4.9)

γ1ie = 1

∀e ∈ E,

(4.10)

γ2ie > f (i) (x) + (γ1ie − 1) M

∀ye ∈ E

(4.11)

γ2ie 6 f (i) (x) + (1 − γ1ie ) M

∀ye ∈ E

(4.12)

γ2ie 6 γ1ie M

∀ye ∈ E

(4.13)

γ1ie ∈ {0, 1}

∀ye ∈ E

(4.14)

i=1


27

γ2ie > 0

∀ye ∈ E

(4.15)

x∈X

(4.16)

di mana M adalah suatu bilangan yang cukup besar. Persamaan (4.8) s/d (4.9) (i) (i) menjamin bahwa βe = min1≤i≤K y (x)yε /∆iε dan Persamaan (4.11) s/d (4.13) menjamin bahwa γ2ie = f (i) (x)γ1ie . Selain variabel awal x dan batasan (4.16), pada masalah P3, dan dengan menambahkan K|E| variabel biner (γ1ie ) , (K+ 1)|E| + 1 variabel kontinu (α, βe , γ2ie dan (4K + 3)|E| batasan linier, di mana |E| adalah kardinalitas dari himpunan E. 4.1.2 Algoritma M-DMA Pendefinisian algoritma M-DMA. Tahap 1. Selesaikan masalah P1 dan misalkan y ∗ = f (x∗ ) adalah nilai optimal. Himpunan E = {y ∗}. Pilih ε ≥ 0. Tahap 2. Selesaikan masalah P3 dan misalkan y ∗ = f (x∗ ) adalah nilai optimal. Tahap 3. Jika α(y ∗) < −ε, maka E = E ∪ y ∗, kembali ke Tahap 1; dalam hal lainnya berhenti. Dalam setiap iterasi algoritma, nilai absolut dari α(y ∗) lebih kecil dari atau sama dengan nilainya dalam iterasi sebelumnya dan titik efisien tunggal ditambahkan pada E. Akibatnya, K variabel biner baru, (K + 1) variabel kontinu baru dan (4K + 3) batasan linier baru ditambahkan. Nilai ini relatip kecil karena jumlah tujuan K kecil pada umumnya. Teorema 2 menunjukkan secara formal bahwa jika ε = 0, maka Algoritma MDMA menentukan batas efisien secara keseluruhan, asalkan jumlah titik efisien


28 berhingga; dalam hal lainnya, aproksimasi-ε atau batas efisien tersaring-ε bisa dihasilkan dengan pilihan ε dan ∆ie yang tepat. Teorema 2. (1) Dalam setiap tahap Algoritma M-DMA, E ⊂ Yeff. (2) Kapan Algoritma M-DMA berakhir. (a) jika ε = 0 maka Yeff = E, yaitu himpunan akhir E adalah batas efisien secara keseluruhan, (i)

(b) jika ∆ie = ye

untuk semua i dan e, maka Aε ⊆ E, di mana ε =

ε/(1 − ε). (i)

(i)

ˆ i untuk semua i dan e serta maxyε ∈E (ye )−minyε ∈E (ye ) > (c) jika ∆ie = R 0 untuk semua i, maka Ee ⊆ E. Bukti. Penyelesaian awal untuk Tahap 0 adalah optimal Pareto. Sisanya diperoleh berasarkan Teorema 1 (Bab 3). Keuntungan utama dari barisan generasi Algoritma M-DMA adalah bahwa di setiap tahap, akan diperoleh himpunan parsial batas efisien yang memuat titik-titik yang terdistribusi dengan baik atas batas efisien total. Dalam banyak masalah tujuan ganda praktis, pengambil keputusan harus mempunyai himpunan penyelesaian-penyelesaian optimal Pareto, yang mana penyelesaian yang diinginkan kemudian dipilih. Akan tetapi, untuk proses seleksi efektif penyelesaian yang diinginkan, himpunan penyelesaian-penyelesaian optimal Pareto haruslah relatip kecil. Untuk ini, kriteria berhenti M-DMA bisa ditingkatkan dan pengambil keputusan bisa mempunyai tiga alternatip :


29 1. menetapkan ε menjadi resolusi yang diinginkan dari batas efisien dan mengoperasikan Algoritma M-DMA; 2. menetapkan ε sama dengan nol dan mengakhiri algoritma bila batas efisien keseluruhan ditemukan atau setelah memperoleh jumlah penyelesaian optimal Pareto yang diinginkan; 3. menetapkan ε sama dengan nol dan mengakhiri algoritma bila batas efisien keseluruhan ditemukan atau setelah jumlah waktu yang ditetapkan sebelumnya.

Pengambil keputusan juga bisa memutuskan menggunakan kriteria penghentian yang mengkombinasikan sebagian atau semua kriteria di atas. M-DMA bisa diaplikasikan pada masalah linier dan juga masalah nonlinier dan pada masalah kontinu atau masalah diskrit. Namun demikian, limitasinya terkait dengan sifat masalah tujuan-tunggal dan juga ukurannya. Menggunakan M-DMA untuk masalah kontinu kurang direkomendasikan karena mengubah sifat masalah menjadi mixed integer.

4.1.3 Contoh Masalah Penjadwalan dalam Optimasi Tujuan Ganda Berikut, contoh masalah penjadwalan dalam optimasi tujuan ganda dengan illustrasi rinci tentang pembentukan batas efisien menggunakan Algoritma M-DMA. Masalahnya adalah untuk menentukan barisan n pekerjaan pada mesin tunggal. Ada tiga tujuan yang dipertimbangkan: rata-rata waktu aliran berbobot, rata-rata keterlambatan dan keterlambatan maksimal. Karena semua tujuan harus diminimalkan, dapat diasumsikan eksistensi perimbangan antara


30 tujuan-tujuan yang dapat diillustrasikan melalui batas efisien. Misalkan pi , µi dan di masing-masing menotasikan lama proses, bobot yang dialokasikan pada lama aliran, dan tenggat waktu pekerjaan i. Tmax adalah keterlambatan maksimal di antara semua pekerjaan dan M adalah bilangan besar. Formulasi pemrograman bilangan bulat (integer programming) dari masalah perangkaian yang dikembangkan, sebagai berikut : [SE]

Min Z = min

n X

µi Ci ,

i=1

n X

Ti, Tmax

!

(4.17)

i=1

Dengan kendala : n X

xij = 1

∀j = 1, . . . , n

(4.18)

i=1 n X

xij = 1

∀j = 1, . . . , n

(4.19)

xkl Pk − (1 − xij ) M

∀i = 1, . . . , n, ∀j = 1, . . . n,

(4.20)

xkl Pk + (1 − xij ) M

∀i = 1, . . . , n, ∀j = 1, . . . n,

(4.21)

j=1

Ci >

j n X X k=1 l=1 j n

Ci 6

XX k=1 l=1

xij ∈ {0, 1}

Ti ≥ Ci di

∀i = 1, . . . , n

(4.22)

Tmax ≥ Ti

∀i = 1, . . . , n

(4.23)

∀i = 1, . . . , n, ∀j = 1, . . . , n

(4.24)

Ti , Ci ≥ 0

(4.25)

∀i = 1, . . . , n

di mana

xij =

   1 jika pekerjaan i dilaksanakan di tempat j   0 dalam hal lainnya


31 Tabel 4.1

Input data dari contoh permasalahan penjadwalan dalam optimasi tujuan ganda Pekerjaan pi µi di

1 4 2 5

2 3 1 8

3 5 3 12

4 8 1 9

5 6 2 10

6 5 4 17

Persamaan (4.17) adalah fungsi tujuan ganda yang memuat tiga tujuan. Fungsi kendala (4.18) dan (4.19) masing-masing menjamin bahwa hanya satu pekerjaan ditempatkan di masing-masing tempat dalam barisan dan bahwa masingmasing pekerjaan hanya dijadwalkan satu kali. Fungsi kendala (4.20) dan (4.21) menetapkan waktu penyelesaian dari masing-masing pekerjaan. Fungsi kendala (4.22) dan (4.23) masing-masing menghitung keterlambatan setiap pekerjaan dan keterlambatan maksimal. Fungsi kendala integralitas diterangkan oleh (4.24) dan fungsi kendala nonnegativitas dari variabel riil diterangkan oleh (4.25). Formulasi SE kemudian dimodifikasi menurut P3 untuk digunakan dalam Algoritma M-DMA; fungsi tujuan dimodifikasi menurut (4.6) dan himpunan fungsi kendala (4.7) s/d (4.16) dimasukkan ke dalam formulasi. Contoh penggunaan Algoritma M-DMA : Misalkan diberikan enam-pekerjaan (input data seperti tertera dalam Tabel 4.1) dengan ε = 0. Penyelesaian pertama diperoleh dengan menyelesaikan P1, seperti yang diajukan di atas. Akibatnya, ditemukan 29 penyelesaian optimal Pareto, seperti yang ditera dalam Tabel 4.2.


32

Tabel 4.2 Titik titik efisiensi Titik Efisiensi Lama proses Lama aliran Tenggat waktu (FT) (Sum T) pekerjaan (Tmax) 1 174 50 22 2 196 35 22 3 264 43 14 4 205 52 19 5 218 44 19 6 237 39 17 7 180 46 22 8 184 52 21 9 190 48 21 10 206 37 21 11 247 41 16 12 184 44 22 13 194 46 21 14 211 48 19 15 231 47 17 16 241 49 16 17 190 43 22 18 200 45 21 19 191 43 22 20 201 42 21 21 232 40 19 22 192 39 22 23 202 41 21 24 207 51 19 25 233 43 17 26 243 45 16 27 172 53 22 28 178 48 22 29 182 55 21 30 188 50 21 Min 172 35 14

Alpha -15.000 -8.000 -0.375 -0.375 -0.294 -0.178 -0.125 -0.125 -0.125 -0.125 -0.118 -0.118 -0.078 -0.067 -0.067 -0.059 -0.059 -0.055 -0.055 -0.055 -0.044 -0.044 -0.044 -0.044 -0.044 -0.022 -0.022 -0.022 -0.022 -


33 Dapat dilihat bahwa nilai absolut α berkurang, diperoleh sebesar 0,0222 untuk titik efisien terakhir. Pada tahap algoritma berikutnya, seperti yang diperkirakan, Penyelesaian 1 diperoleh lagi-lagi dengan α = 0, yang mengindikasikan akhir prosedur. Pertama, kita peroleh penyelesaian optimal untuk Masalah P1 (Penyelesaian 1 dalam Tabel 4.2 dan titik tebal dalam Gambar 4.1(a)). Penyelesaian hampir optimal dalam fungsi tujuan rataan lama-aliran berbobot (174 versus nilai optimal 172). Kedua penyelesaian berikutnya memuat nilai optimal (minimal) dari tujuan lainnya: 35 dan 14 masing-masing untuk mean keterlambatan dan keterlambatan maksimum (Penyelesaian 2 dan 3 dalam Tabel 4.2 dan titik-titik berlubang dalam Gambar 4.1(a)). Gambar 4.1(a) s/d 4.1(c) menunjukkan secara grafik perkembangan batas efisien di mana titik-titik tebal menyatakan penyelesaian yang ada dan titik-titik berlubang adalah penyelesaian yang baru dihasilkan. Dalam Gambar 4.1(d), diperlihatkan batas efisien keseluruhan. Dapat dilihat bahwa karena Algoritma M-DMA menghasilkan penyelesaian yang jauh dari penyelesaian yang ada saat ini, algoritma mula-mula menghasilkan penyelesaian yang optimal dalam tujuan-tujuan yang berbeda dan ditempatkan di tepi batas efisien (Gambar 4.1(a)). Akibatnya, algoritma terus menambahkan titik-titik yang tersebar merata pada rentang batas efisien sampai batas efisien sepenuhnya diperoleh (Gambar 4.1(d)). Dalam kasus prosedur berakhir dengan himpunan parsial, sangat penting dipahami konsekuensi dari tidak mempunyai batas efisien penuh ada kualitas himpunan yang diperoleh. Misalnya, ditetapkan ε = 0, 1, dalam contoh penjad-


34 Gambar 4.1 Pengembangan perbatasan efisiensi dari contoh kasus dengan menggunakan M-DMA

î ) walan di atas. Dalam kasus ini, tetapkan Fε (karena kita gunakan ∆ie = R akan memuat 13 titik pertama. Titik ke empat belas dan seterusnya tidak akan tercakup dalam himpunan ini karena untuk setiap satu titik ini, α(y) > −ε. Perhatikan y dengan −ε < α(y) < 0. Titik ini efisien tetapi tidak tercakup di dalam Fε . Karena titik ini efisien, titik ini lebih baik (lebih kecil) daripada setiap titik lainnya dalam Fε setidaknya dalam satu tujuan. Fakta bahwa α(y) lebih besar dari (−ε) menjamin bahwa terdapat suatu titik dalam himpunan Fε yang tidak lebih buruk daripada y, dalam setiap tujuan, lebih dari ε kali rentang tujuan. Dengan kata lain, terdapat beberapa yε dalam himpunan Fε untuk mana (i)

(yε y (i))/Ri /leqε untuk setiap i. Akibatnya, nilai ε menjamin bahwa kehilangan resolusi, dalam batas efisien parsial tidak akan melebihi konstanta yang diberikan ˆ i ≤ Ri , dapat digunakan R ˆ i seεRi , dalam setiap tujuan. Catat bahwa karena R bagai pengganti Ri sebagai koefisien penentuan skala yang menjamin setidaknya


35 resolusi yang sama.

4.2 Formulasi Pemrograman Cabang dan Batas (Branch-and-Bound B&B) Pemrograman Cabang dan Batas (B&B) adalah pendekatan umum untuk menyelesaikan masalah kombinatorial tujuan-tunggal. Ada beberapa tipe B&B; semuanya didasarkan pada pencabangan pohon pencarian sambil menghasilkan penyelesaian parsial. Dengan mengasumsikan masalah minimisasi, yang didasarkan pada perbandingan antara batas bawah penyelesaian parsial dan batas atas yang diperoleh dari penyelesaian layak yang ada saat ini, cabang yang tidak bisa menghasilkan penyelesaian optimal diukur. Dalam masalah tujuan ganda, batas haruslah dikembangkan untuk setiap tujuan dan cabang bisa diukur hanya bila didominasi oleh penyelesaian layak, yaitu bila batas bawah dari semua tujuan sama dengan atau lebih besar dari tujuan dari penyelesaian yang ada. Aspek penting lainnya dalam keberhasilan implementasi B&B adalah rangkaian percabangan. Dalam masalah tujuan-tunggal, sangat umum lebih menginginkan pengembangan satu penyelesaian parsial ketimbang yang lainnya yang didasarkan pada batas yang dihitung. Karena beberapa batas dihasilkan untuk setiap node dalam masalah multitujuan, kaidah preferensi yang berbeda haruslah diajukan. Misalkan x ˆ adalah penyelesaian parsial pada pohon B&B. Misalkan α(ˆ x) adalah α minimal dari penyelesaian yang memuat penyelesaian parsial x ˆ. Kemudian batas batas untuk α(ˆ x), α ˆ (ˆ x) bisa dihitung dengan persamaan berikut: ! (i) (i) ˆ f (ˆ x) − ye min (4.26) α ˆ (ˆ x) = max ye ∈E 16i6K ∆ie


36 x) adalah batas bawah dari tujuan ke-i untuk penyelesaian parsial x ˆ di mana fˆ(i) (ˆ dan E 6= ∅, seperti yang ditunjukkan dalam deskripsi algoritma di bawah. Dalam pendekatan yang diajukan, dengan menggunakan α(ˆ ˆ x) akan menjadikan prosedur penentuan batas efisien sangat mirip dengan B&B tujuan-tunggal. Namun demikian, ketimbang menentukan penyelesaian optimal, semua titik efisien dihasilkan. Mula-mula ditetapkan algoritma dasar dengan himpunan penyelesaian layak E. Kemudian diperiksa bahwa tak satupun penyelesaian dalam himpunan E didominasi penyelesaian lainnya dalam himpunan ini. Himpunan E dimutakhirkan berulang kali selama operasi algoritma. Bila ada perubahan dalam himpunan, Persamaan (4.26) dihitung ulang, dan batas bawah ditingkatkan (nilai α(ˆ ˆ x) hanya bisa meningkat atau tetap tak berubah). Bila nilai mininal dari α(ˆ ˆ x) sama dengan atau lebih besar dari nol, maka batas efisien dalam ruang tujuan ditentukan. Analog dengan Algoritma M-DMA, algoritma B&B juga bisa disesuaikan untuk menggunakan ε. Tahap-tahap utama dari Algoritma B-DMA adalah sebagai berikut : 1.) Penentuan Penyelesaian Awal Himpunan awal E bisa mencakup satu atau lebih penyelesaian layak, namun tak satupun di antaranya didominasi penyelesaian lainnya dalam himpunan. Jika masalah tujuan ganda bisa diselesaikan dengan mudah sewaktu mempertimbangkan seitap tujuan tunggal dari K tujuan, direkomendasikan untuk mencakup penyelesaian tujuan-tunggal ini dalam himpunan E. Jika tidak ada penyelesaian layak, bisa digunakan penyelesaian dummy, dengan menggunakan batas atas pada tujuan sebagai batas awal.


37 2.) Prosedur Pencabangan Prosedur pencabangan eksak tergantung pada implementasi B&B, misalnya kaidah batas terbaru atau batas terbaik pertama atau setiap variasi B&B lainnya diaplikasikan. Seperti yang disebutkan di atas, α ˆ (ˆ x) dan α(ˆ x) dari masalah tujuan ganda ekuivalen dengan batas bawah dan fungsi tujuan dalam masalah tujuan-tunggal. Setiap kali penyelesaian layak x diperoleh, himpunan E harus di-mutakhirkan sebagai berikut:

a). jika α(x) < 0, kemudian E = E ∪ f(x), b). untuk setiap ye ∈ E, jika ye didominasi oleh f (x), kemudian E = E\ye , kemudian α ˆ (ˆ x), selanjutnya dihitung kembali untuk semua node terbuka (node tanpa pendahulu).

3.) Kaidah Pengukuran Untuk setiap kandidat penyelesaian parsial x ˆ, nilai α(ˆ ˆ x) diperiksa. Jika α(ˆ ˆ x) ≥ 0, dapat disimpulkan bahwa penyelesaian parsial ini sama dengan atau didominasi oleh suatu penyelesaian di dalam E. Karena batas efisien parsial hanya bisa ditingkatkan selama waktu tersisa dari operasi algoritma, penyelesaian parsial tidak bisa menghasilkan penyelesaian baru dalam batas efisien dalam ruang tujuan, dan cabangnya diukur. 4.) Syarat Ujung Jika tidak ada kandidat untuk melanjutkan proses rancangan, maka berhenti; dalam hal lainnya lanjutkan dengan prosedur pencabangan dan pengukuran. Teorema 3. Bila Algoritma B-DMA berakhir, Yeff = E, yaitu himpunan akhir E


38 adalah batas efisien total. Bukti. Algoritma B-DMA bila semua cabang diukur, yaitu setiap penyelesaian parsial x ˆ mempunyai α(ˆ ˆ x) ≥ 0. Karena α(ˆ ˆ x) adalah batas bawah atas α(x), di mana x adalah suatu penyelesaian yang dihasilkan dari penyelesaian parsial x ˆ, juga α(x) ≥ 0. Fakta ini bersama-sama dengan Teorema 1 melengkapi bukti.

Ada beberapa keuntungan yang diharapkan dengan menggunakan α(x) dan batas bawah atas α(x) dalam algoritma B&B. Pertama, himpunan E memuat himpunan penyelesaian yang beranekaragam, di setiap tahap algoritma. Tentu saja, berbeda dengan M-DMA, seperti yang disebutkan dalam Teorema 3, penyelesaian dalam himpunan E terbukti optimal Pareto hanya di akhir operasi algoritma. Selain itu, dapat dikatakan bahwa keanekaragaman penyelesaian parsial menjamin bahwa semua batas ditingkatkan secara simultan, yang bisa menyebabkan pengukuran cabang-cabang dengan lebih cepat. Akibatnya, diharapkan pencarian beranekaragam, seperti yang dilakukan di sini (berbeda, misalnya, dengan pencarian neighborhood) untuk membawa ke daerah probabilitas yang lebih tinggi untuk menentukan penyelesaian optimal Pareto baru. Contoh penjadwalan berikut mengklarifikasi implementasi cabang-dan-batas DMA, dan menunjukkan kelebihan-kelebihannya. Tipe B&B yang digunakan di sini adalah batas terbaik pertama menurut mana setiap kali node dengan batas bawah terkecil dikembangkan (ikatan dirusak secara acak). Masalah yang diselesaikan di sini adalah versi lebih kecil dari masalah yang diselesaikan sebelumnya


39 dengan M-DMA, yang hanya mencakup lima pekerjaan pertama. Operasi algoritma rinci digambarkan dalam Tabel 4.3. Kolom kedua menggambarkan jumlah tahap/iterasi algoritma; di setiap iterasi dibentuk node baru penyelesaian (parsial). Kolom pertama mencakup pointer ke tahap sebelumnya (induk). Kolom ketiga mencakup pointer ke penyelesaian dalam himpunan E. Kolom keempat memuat barisan pekerjaan dalam penyelesaian (parsial). Seperti yang bisa dilihat, pekerjaan-pekerjaan dijadwalkan dari akhir ke awal rangkaian. Ini bisa dilakukan karena waktu setiap pekerjaan, dan juga rentang pembuatan, tidak tergantung barisan. Kolom kelima memuat nilai (batas bawah untuk) tujuan, dari setiap penyelesaian (parsial). Kolom terakhir memuat batas bawah untuk α dari setiap penyelesaian parsial. Karena setiap kali himpunan E dimutakhirkan, batas bawah dihitung ulang dan dapat dilihat trend peningkatan batas bawah dari setiap penyelesaian parsial. Lambang-lambang lainnya dijelaskan di bagian bawah dari Tabel 4.3 bagian pertama.


40 Tabel 4.3 Contoh Kasus Penerapan Algoritma B-DMA


41 Keterangan : S : Solusi akhir dalam E

S-D : Solusi akhir yang terdominasi

C : Solusi parsial yang berkelanjutan

X

: Solusi parsial yang terukur

Algoritma dimulai dengan dua penyelesaian layak, yang pertama diperoleh dengan mengaplikasikan kaidah perangkaian WSPT (waktu pemrosesan terpendek berbobot) dan kedua dengan mengaplikasikan kaidah EDD (diharuskan paling awal). Dapat dilihat bahwa harus dihasilkan sebanyak 18 penyelesaian (dari 120 penyelesaian layak) untuk menentukan batas efisien total, dan 73 node harus dibentuk dalam pohon pencarian. Tujuh dari 18 penyelesaian ditentukan efisien (lihat baris abuabu dalam Tabel 4.3). Juga dapat dilihat bahwa dengan menggunakan batas terbaik pertama B-DMA berbasis-B&B, dibutuhkan waktu untuk mencari penyelesaian pertama untuk himpunan E (di luar penyelesaian layak awal). Akan tetapi, sesudah itu cabang-cabang diukur relatip dini begitu himpunan E dimutakhirkan dan prosedur berakhir dengan sangat cepat. Dalam Gambar 4.5, memperlihatkan presentasi grafik dari pengembangan batas efisien dengan menggunakan B-DMA. Dapat dilihat bahwa rangkaian penentuan penyelesaian optimal Pareto sangat mirip dengan rangkaian yang dilihat dengan M-DMA dalam arti keanekaragaman penyelesaian parsial selama operasi algoritma. Titik-titik cahaya pada masing-masing grafik menyatakan penyelesaian yang dihasilkan terakhir. Dimulai dengan dua penyelesaian yang optimal dalam keterlambatan maksimal dan mean waktu aliran berbobot, penyelesaian tambahan pertama ditentukan kemudian sebagai optimal dalam tujuan ketiga, mean keterlambatan. Kemudian, setelah membentuk bentuk segitiga batas efisien yang diperkirakan, penyelesaian lain ditentukan di antara penyelesaian-penyelesaian


42 yang ditentukan sebelumnya sampai batas efisien total diperoleh. Yang menarik, dapat dilihat bahwa salah satu penyelesaian yang dihilangkan kemudian dari himpunan E: walaupun penyelesaian optimal dalam keterlambatan maksimal, penyelesaian lain ditemukan, juga optimal dalam keterlambatan maksimal, tetapi lebih baik dalam tujuan lainnya. Implementasi B-DMA berskala besar bisa ditemukan dalam Bukchin dan Masin (2004). Gambar 4.2

Pengembangan Perbatasan Efisiensi dari Contoh Kasus dengan Menggunakan B-DMA


BAB 5 KESIMPULAN DAN SARAN

5.1 Kesimpulan Dalam penelitian ini, dikembangkan pendekatan baru yang disebut pendekatan maksimisasi keanekaragaman (DMA) untuk menghasilkan batas efisien masalah optimisasi multi-tujuan. Pendekatan yang diajukan menentukan semua titik efisien untuk masalah multitujuan umum. Dalam kasus jumlah titik efisien terlalu besar bagi pengambil keputusan, diperoleh batas efisien parsial, yang menangkap perimbangan antara tujuan-tujuan yang berbeda dengan cara yang serupa dengan batas efisien total. Untuk ini, sewaktu mencari penyelesaian optimal Pareto berikutnya, DMA bertujuan menentukan penyelesaian paling beranekaragam. Ini dilakukan dengan mencari titik efisien yang terjauh dari titik efisien terdekat yang sudah ada di batas efisien. Akibatnya, batas efisien parsial bisa dipersepsikan sebagai himpunan batas efisien total tersaring. Pendekatan yang diajukan bisa diaplikasikan pada setiap masalah yang bisa diselesaikan untuk kasus tujuan tunggal. Pendekatan DMA diimplementasikan mula-mula secara langsung pada formulasi MIP masalah awal, yang melibatkan ukuran keanekaragaman yang baru diajukan. Selanjutnya, tipe implementasi lainnya atas cabang dan batas terorientasi masalah dipresentasikan.

43 Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

44 5.2 Saran Sebagai penelitian lebih lanjut, dapat dikembangkan implementasi DMA untuk masalah multitujuan yang berbeda dan kombinasi ukuran keanekaragaman DMA dengan meta-heuristik. Selain itu, penggunaan DMA secara interaktif dengan pengambil keputusan. Akibatnya, pencarian menjadi lebih efektif karena dapat lebih fokus pada bagian-bagian relevan dari batas efisien.


DAFTAR PUSTAKA

Chankong, V., Y. Y. Haimes, (1983) Multiobjective Decision Making Theory and Methodology, North-Holland, New York, . Cohon, J. L. (1985) Multicriteria programming : Brief Review and Application. J. S. Gero, ed.Design Optimization. Academic Press, New York, 163-191,. Das, I., J. E. Dennis, (1998) Normal-Boundary Intersection : A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems, SIAM J. Optimation 8(3) 631-657, . Deb. K. (2001) Multi-objective Optimization using Evolutionary Algorithms, Chichester, UK : Wiley, . Deb. K., M. Mohan. S. Mishra. (2003)Toward a Quick Computation of Well-Spread Pareto- Optimal Solution, C. M. Fonseca, P. J. Fleming, E. Zitzler, K. Deb, L. Thile, eds. Evolutionary Multi-Criterion Optimization, Second Internat, Conf., Lecture Notes in Computer Science, Vol. 2632, Springer, Faro, Portugal, 222-236,. De Jong, E. D., Pollack, J. B., (2003)Multi-objective Methods for Tree Size Control, Genetic Programming and Evoluable Machines, 4 (3) 2ll-233. De Jong, E. D., Watson, R. A., and Pollack, J. B., (2001) Reducing Bloat and Promoting Diversity using Multi-objective Methods, In L. Spector et al. (Ed.), Proceedings of the Genetic and, Evolutionary Computation Conference, GECCO-0l, pp. 11.-18, San Flancisco, CA. Morgan Kaufrnann,. Ehrgott, M., X. Gandibleux, (2002) Multiobjective Combinatorial Combinatorial Optimization-Theory, Methodology, and Applications, Multiple Criteria Optimization-State of the Art Annotated Bibliography Survey, Kluwer Academic Publishers, Boston, MA, 369-444, . Goldberg, D. E., Richardson, J. (1987). Genetic Algorithms with Sharing for Multimodal Function Optimization, In Grefenstette, J. J. (Ed.), Genetic Algorithrns and their Applications : Proc. of the second Int. Conf. on Genetic Algorithms, pp 41-49, Hillsdale, NJ.Lawrence Erlbaum Associates, 2001. Holland, J. H., (1975) Adaptation in Natural and Artifical Systems, University of Michigan Press, Ann Arbor, MI, . Laumanns, M., Thiele, L., Zitzler,E., Deb, K., (2001) On the Convergence and Diversity Preservation Properties of Multi-Objective Evolutionary Algorithms, TIK Report No. 108, Switzerland, . Messac, A., C. A. Mattson, (2002) Generating Well-Distributed Sets of Pareto Point for Enggineering Design using Physical Programming, Optimization Enggineering 3 431-450, .

45 Daswati Sigalingging : Pendekatan Maksimasi Diversitas Untuk Optimasi Tujuan Ganda (Multi-Objective), 2009 USU Repository © 2008

46 Steuer, R. E., (1986) Multiple Criteria Optimization : Theory, Computation and Application, Wiley Series in Probability and Mathematical Statistics, John Wiley, New York, . Van Veldhuizen, D., Lamont, G., (2000) On Measuring Multiobjective Evolutionary Algorithms Performance, Congress on Evolutionary Computation, CEC 2000, Piscataway, NJ, . Toffolo, A., and Benini, E., (2003) Genetic Diversity as an Objective in MultiObjective Evolutionary Algorithms, Evolutionary Computation, Vol. 11, No. 2, . Yuan, B., Gallagher, M., (2005) On the Importance of Diversity Maintenance in Estimation of Distribution Algorithms, ln Procedings of the 2005 Conference on Genetic and Evolutionary Computation, pp. 719-726, . Zitzler, E., Deb, K., Thiele, L, (2000)Comparison of Multiobjective Evolutionary Algorithms : Empirical Results, Evolutionary Computation, Vol. 8, No. 2, .


PENDEKATAN MAKSIMASI DIVERSITAS UNTUK OPTIMASI TUJUAN GANDA (MULTI-OBJECTIVE)

Recommend Documents