Hasil Pencarian  ::  Simpan CSV :: Kembali

"Salah satu dari masalah-masalah dominan pada komputasi biologi molekuler adalah penyejajaran barisan berganda (Multiple Sequence Alignment - MSA) dari DNA. Banyak metode yang telah diajukan untuk menyelesaikan masalah MSA seperti pemrograman dinamik dan heuristik. Satu metode telah diajukan oleh Althaus et al. untuk menyelesaikan masalah MSA yang didasarkan pada pemrograman linear bilangan bulat (Integer Linear Programming - ILP). Formulasi ILP umum dari masalah MSA diturunkan dari representasi graf dari masalah MSA. Walaupun formulasi ILP umum dari masalah MSA diketahui, membentuk model ILP dari suatu masalah MSA yang dapat diselesaikan langsung menggunakan suatu solver ILP tidaklah mudah. Sebuah program yang dapat membangun dan menyelesaikan model ILP dari sebuah masalah MSA menggunakan MATLAB telah dibuat. Metode yang digunakan untuk menyelesaikan model ILP tersebut adalah branch-and-bound. Program yang telah dibuat dapat menghasilkan model ILP dari sembarang masalah MSA yang diberikan tetapi hanya dapat menyelesaikan masalah MSA dari sejumlah kecil barisanbarisan DNA yang pendek. Hasil dari program tersebut adalah penejajaran barisan-barisan DNA dari masalah MSA yang diberikan.

---

One of the dominant problems in computational molecular biology is multiple sequence alignment (MSA) of DNA. Many methods have been proposed to solve MSA problem such as dynamic programming and heuristic. A method has been proposed by Althaus et al. to solve MSA problem which is based on integer linear programming (ILP). The general ILP formulation of the MSA is derived from the graph representation of the MSA problem. Although we have the general ILP formulation of the MSA problem, constructing the ILP model of an MSA that can be solved directly using an ILP solver is not straightforward. We develop a MATLAB program that can generate and solve the ILP model of an MSA problem. The method that is used to solve the ILP model is branch-and-bound. The constructed program can generate the ILP model of any given MSA problem but can only solve an MSA problem of a small number of short DNA sequences. The result of the program is the aligned sequences of the MSA problem."

"Generalized Assignment Problem (GAP) adalah masalah penugasan sejumlah berhingga tugas pada sejumlah berhingga agen, dimana sebuah tugas harus dikerjakan oleh satu agen, tetapi satu agen dapat mengerjakan lebih dari satu tugas. Setiap agen mempunyai kapasitas dan setiap tugas mempunyai bobot, yang mungkin berbeda untuk setiap agen. Pada skripsi ini akan dilihat kinerja dari algoritma MAX-MIN Ant System (MMAS) dengan Local Search dalam menyelesaikan GAP, yang diukur berdasarkan kedekatan solusi yang didapatkan dengan best known solution. MMAS adalah pengembangan dari Ant System Algorithm, yaitu algoritma yang diinspirasikan oleh perilaku semut-semut di dunia nyata. Dalam algoritma ini terdapat parameter ??, Q, ??, dan p0 yang harus ditentukan, yang diambil menurut rekomendasi St??tzle dan Hoos. Lalu nilai dari parameter Q, ??, dan p0 akan diubah untuk mengetahui pengaruhnya terhadap kinerja algoritma MMAS dengan Local Search. Masalah pengujian diambil dari OR-Library. Berdasarkan simulasi, disimpulkan bahwa kinerja algoritma MMAS dengan Local Search dalam menyelesaikan GAP cukup baik dengan error relatif cukup kecil, yaitu tidak lebih dari 0.04 dan perubahan nilai parameter dapat membawa perbaikan pada solusi."

"Generalized Assignment Problem (GAP) adalah masalah penugasan sehimpunan berhingga agen ke sehimpunan berhingga pekerjaan. Setiap pekerjaan mempunyai bobot dan setiap agen mempunyai kapasitas, sehingga setiap agen tidak dapat mengerjakan seluruh pekerjaan, tergantung kepada kapasitas yang dimiliki. Ada biaya yang harus dikeluarkan jika agen mengerjakan suatu pekerjaan. Pada skripsi ini akan dilihat kinerja dari algoritma Greedy Randomized Adaptive Search Procedure (GRASP) dalam menyelesaikan GAP. Algoritma GRASP terdiri dari 2 fase, yaitu fase konstruksi solusi awal dengan algoritma Greedy Randomized Adaptive Heuristics (GRAH) dan fase perbaikan dengan metode local search. Kinerja dari algoritma GRASP akan diukur berdasarkan kedekatan solusi yang diperoleh dengan Best Known Solution (BKS). Data masalah untuk menguji diambil dari OR Library. Berdasarkan hasil percobaan, dapat disimpulkan bahwa kinerja Algoritma GRASP dalam menyelesaikan GAP cukup baik untuk masalah GAP berukuran kecil, yaitu berukuran 5 x 15, 5 x 20, 5 x 25, 5 x 30, 8 x 24, 8 x 32."

"Generalized Assignment Problem (GAP) adalah masalah penugasan sejumlah berhingga tugas pada sejumlah berhingga agen, dimana sebuah tugas harus dikerjakan tepat oleh satu agen, tetapi satu agen dapat mengerjakan lebih dari satu tugas. Setiap agen mempunyai kapasitas, dan setiap tugas mempunyai bobot, yang mungkin berbeda untuk setiap agen. Pada skripsi ini akan dilihat kinerja algoritma Simulated Annealing (SA) dalam menyelesaikan GAP, yang diukur berdasarkan kedekatan solusi yang diperoleh dengan best known solution (BKS) dari masalah penguji yang diambil dari OR-Library. Metode SA merupakan pengembangan dari metode local search (LS). Pencarian dengan algoritma SA berusaha keluar dari optimum lokal dari LS dengan memperbolehkan pencarian ke solusi yang tidak lebih baik dengan probabilitas tertentu yang dipengaruhi oleh temperatur. Dari simulasi yang telah dilakukan, dapat dikatakan bahwa algoritma SA cukup baik dalam menyelesaikan GAP dimana kesalahan relatif kurang dari 0,05. "

"Generalized Assignment Problem (GAP) adalah masalah penugasan sehimpunan berhingga tugas ke sehimpunan berhingga agen. Setiap tugas mempunyai bobot dan biaya penyelesaian yang mungkin berbeda untuk setiap agen. Setiap agen mempunyai kapasitas sumber daya dan tidak boleh mengerjakan tugas melebihi kapasitasnya. Pada skripsi ini dilihat kinerja dari algoritma genetik dalam menyelesaikan GAP. Algoritma genetik terinspirasi oleh teori evolusi biologi. Operator utama yang digunakan adalah binary tournament selection, one point crossover, dan swap mutation. Untuk meningkatkan kinerja, ditambahkan local improvement steps dan replacement scheme. Kinerja algoritma genetik diukur dari kedekatan solusi yang diperoleh dengan Best Known Solution (BKS) dari masalah penguji yang diambil dari OR Library. Selain itu, juga dilihat pengaruh perubahan nilai probabilitas crossover PC dan probabilitas mutasi Pm terhadap kinerja algoritma genetik. Berdasarkan percobaan, disimpulkan bahwa kinerja algoritma genetik dalam menyelesaikan GAP cukup baik, dengan kesalahan relatif nilai fungsi tujuan solusi terbaik terhadap BKS cukup kecil, yaitu tidak lebih dari 0.03. Dari percobaan mengubah nilai parameter, diperoleh dengan PC = 0.6, nilai Pm yang cukup baik adalah 0.25 ? 0.3. "

"Treveling salesman problem (TSP) adalah masalah mencari rute perjalanan melewati sejumlah berhingga tempat dengan syarat setiap tempathanya dikunjungi tepat satu kali dan perjalanan berawal dan berakhir di satu tempat. TSP berdasarkan kesimetrian terbagi menjadi TSP simetrik dan TSP asimetrik adalah TSP dimana bobot busur tidak bergantung pada arahan pembusuran ..."

"Misalkan G = (V,E) adalah graf sederhana dengan v simpul dan e busur. Pelabelan total busur ajaib pada graf G adalah pemetaan bijektif f dari VUE ke himpunan bilangan bulat positif berurutan { 1,2,3, ..., v+e } sehingga bobot semua busur adalah konstan. Pelabelan total busur ajaib dengan f (E) = { b+1,b+2,b+3, ..., b+e },0 <_ b <_ v disebut pelabelan total busur-ajaib b-busur berurutan. Jika suatu graf memiliki pelabelan total busur-ajaib b-busur berurutan maka banyak maksimum busur pada G adalah v - 1 atau dengan kata lain e <_ v - 1. Suatu graf dengan e > v - 1 masih bisa dilabel dengan pelabelan total busur-ajaib b-busur berurutan dengan menambahkan sejumlah simpul terisolasi sehingga memenuhi e <_ v - 1. Pada makalah ini akan dikonstruksi pelabelan total busur-ajaib b-busur berurutan untuk graf kecebong dan graf dumbbell dengan menambahkan simpul-simpul terisolasi sehingga memenuhi e <_ v - 1.

---

Let G = (V,E) be a simple graph with v vertices and e edges. An edge magic total labeling of a graph G is a bijection f from VUE onto the set of consecutive positive integers { 1,2,3, ..., v+e } so that the weight of all edges are constant. An edge magic total labeling with f (E) = { b+1,b+2,b+3, ..., b+e } 0 <_ b <_ v is called b-edge consecutive edge magic total labeling. If a graph has a b-edge consecutive edge magic total labeling, then the maximum number of edges in G is v - 1 or e <_ v - 1. A graph with e > v - 1 can be labeled with b-edge consecutive edge magic total labeling by adding some isolated vertices to G in order to satisfy e <_ v - 1. In this skripsi we give the construction of a b-edge consecutive edge magic total labeling on tadpole graphs and dumbbell graphs by adding some isolated vertices to satisfy e <_ v - 1."