Showing posts with label bài tập java. Show all posts
Showing posts with label bài tập java. Show all posts

Giải thuật di truyền giải bài toán người du lịch (TSP)

in , , , , , , , /

Giải thuật (thuật toán) di truyền (GA).

Thuật toán di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.

Di truyền là hiện tượng chuyển những tính trạng của cha mẹ cho con cái thông qua gen của bố mẹ. Trong sinh học, di truyền chuyển những đặc trưng sinh học từ một sinh vật cha mẹ đến con cái và nó đồng nghĩa với di chuyển gen, gen thừa nhận mang thông tin sinh học hay thông tin di truyền.

Tiến hóa nói đến quá trình hoàn thiện, biến đổi dần để hoàn thiện hơn các bộ phận, chức năng của các sinh vật để phù hợp hơn với điều kiện sinh tồn. Trong sinh học, tiến hóa là sự thay đổi đặc tính di truyền của một quần thể sinh học qua những thế hệ nối tiếp nhau. Các quá trình tiến hóa làm nảy sinh sự đa dạng ở mọi mức độ tổ chức sinh học bao gồm loài, các cá thể sinh vật và cả các phân tử như ADN và protein.

Giải thuật di truyền (GA) là phương pháp tìm kiếm tối ưu ngẫu nhiên bằng cách mô phỏng theo sự tiến hóa của con người hay của sinh vật. GA được ứng dụng rộng rãi trong giải quyết các bài toán tối ưu, như bài toán người du lịch, bài toán người bán hàng, và nhiều bài toán khác.

 

Bài toán người du lịch

Bài toán người du lịch là một bài toán quan trọng trong lĩnh vực tối ưu hóa và khoa học máy tính. Hãy cùng tìm hiểu về nó!

Mô tả bài toán:

+ Một người du lịch muốn thăm quan n thành phố T1, T2, …, Tn.

+ Người du lịch xuất phát từ một thành phố bất kỳ và muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua duy nhất một lần rồi quay trở lại thành phố xuất phát.

+ Gọi Cij là chi phí đi từ thành phố Ti đến Tj.

+ Yêu cầu: Tìm một hành trình thỏa mãn yêu cầu trên sao cho tổng chi phí là nhỏ nhất.

 

Thuật toán GA giải bài toán người du lịch

Bước 1: Tạo quần thể

Bước 2: Đánh giá

- Thoả mãn điều kiện (tìm được giá trị độ dài quãng được tốt nhất (nhỏ nhất) hoặc tiến hoá đủ 1000 thế hệ (số thế hệ do người dung thiết lập)) => Bước 6

-  Chưa thoả điều kiện => Bước 3

Bước 3: Lựa chọn (chọn các cá thể có độ thích nghi tốt nhất (quãng đường ngắn nhất) => Bước 4

Bước 4: Lai ghép => Bước 5

Bước 5: Đột biến => Bước 2 (lặp lại)

Bước 6: Kết thúc.

Cài đặt thuật toán bằng Java

1- Tạo Project

 


2- Class GA

 







3- Class GATSP (class main)

 


4- Kết quả




Kết luận:

Thuật toán di truyền (Genetic Algorithm - GA) là một phương pháp tối ưu hóa dựa trên nguyên tắc của tiến hóa sinh học. Dưới đây là một số ứng dụng thú vị của thuật toán di truyền:

- Giải bài toán người du lịch (Traveling Salesman Problem - TSP): Trong bài toán này, người du lịch cần tìm hành trình qua tất cả các thành phố một lần duy nhất và quay trở lại thành phố xuất phát sao cho tổng chi phí là nhỏ nhất. GA có thể áp dụng để tìm lời giải gần đúng cho TSP.

- Tối ưu hóa hàm số: GA có thể tìm kiếm giá trị tối ưu của hàm số trong không gian nhiều biến.

- Lập lịch sản xuất: Trong việc lập lịch sản xuất, GA có thể tối ưu hóa thời gian sản xuất, tối thiểu hóa chi phí và tối đa hóa hiệu suất.

- Thiết kế mạng neuron: GA có thể tối ưu hóa trọng số của mạng neuron để đạt được hiệu suất tốt nhất.

- Tối ưu hóa kích thước bộ lọc trong xử lý ảnh: GA có thể tìm kích thước và hình dạng của bộ lọc để cải thiện chất lượng ảnh.

- Tối ưu hóa các tham số trong máy học: GA có thể tìm giá trị tối ưu cho các tham số của mô hình máy học.

Thuật toán di truyền là một công cụ mạnh mẽ để giải quyết các bài toán tối ưu và tìm kiếm lời giải gần đúng trong nhiều lĩnh vực khác nhau.

* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*

Ví dụ Xây dựng mảng đối tượng trọng trong Java

in , , , , /

Xây dựng project theo mô hình kế thừa:

Yêu cầu:

1. Nhập thông tin cho n sinh viên (3<n<30)

2. In ra danh sách sinh viên có điểm chữ là A

3. Đổi tên tên cả sinh viên thành chữ in hoa

--------------------

Một số tài liệu và khoá học bổ ích dành cho bạn: 

# Tài liệu: Lập trình hướng đối tượng JAVA core dành cho người mới bắt đầu học lập trình [Click để xem]

# Khoá học online: Lập trình Java trong 4 tuần [Click để xem]


Xây dựng project với các lớp theo hình vẽ dưới đây


Code:

// class SV
package vd_adstract_130114;
import java.util.Scanner;

 abstract class SV {
    String hoTen, diaChi,he;
    int namSinh;
    // phuong thuc khoi tao
    public SV(String hoTen, String diaChi,String he,int namSinh){
        this.hoTen=hoTen;
        this.diaChi=diaChi;
        this.he=he;
        this.namSinh=namSinh;
    }
    
    // Tinh diem
    abstract float TinhDiem();
    // diem chu
    char DiemChu(){
        float diem=TinhDiem();
        char dchu;
        if(diem<4)
            dchu='F';
        else if(diem<5.5)
            dchu='D';
        else if(diem<7)
            dchu='C';
        else if(diem<8.5)
            dchu='B';
        else dchu='A';
        
        return dchu;
    }
    // in ket qua
    void InKQ(){
        System.out.print("\n\n IN KET QUA SINH VIEN "+he);
        System.out.print("\n + Ho ten: "+hoTen);
        System.out.print("\n + Dia chi: "+diaChi);
        System.out.print("\n + Nam sinh: "+namSinh);
        System.out.print("\n + Diem tong ket: "+TinhDiem());
        System.out.println("\n + Diem chu: "+DiemChu());        
    }
}


// class SVCD

package vd_adstract_130114;

class SVCD extends SV{
    float dTA,dToan,dLT,dCSDL;
    // khoi tao
    public SVCD(String hoTen, String diaChi,String he,int namSinh,float dTA, float dToan,float dLT,float dCSDL){
        super(hoTen,diaChi,he,namSinh);
        this.dCSDL=dCSDL;
        this.dLT=dLT;
        this.dTA=dTA;
        this.dToan=dToan;
    }

 
 
    // Tinh diem
    float TinhDiem(){
        return (dTA*2+dToan*2+dLT*3+dCSDL*2)/10;
    }

}


// class SVDH

 package vd_adstract_130114;
public class SVDH extends SV {
    float dTA,dToan,dLT,dCSDL,dTTNT;
    // khoi tao
    public SVDH(String hoTen, String diaChi,String he,int namSinh,float dTA, float dToan,float dLT,float dCSDL,float dTTNT){
        super(hoTen,diaChi,he,namSinh);
        this.dCSDL=dCSDL;
        this.dLT=dLT;
        this.dTA=dTA;
        this.dToan=dToan;
    }
    // Tinh diem
    float TinhDiem(){
        return (dTA*2+dToan*2+dLT*3+dCSDL*2+dTTNT*2)/12;
    }
}



// class _adstract_130114 (class main)
package vd_adstract_130114;
import java.util.Scanner;
/**
 *
 * @author tranxuanthanh
 */
public class Vd_adstract_130114 {

     /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
        
        // khai bao mang doi tuong
        SV[] a =new SV[30];
        // Nhap thong tin sinh vien
        System.out.print("\n Chon he sinh vien \n 1 - Dai hoc; \n 2 - Cao dang; \n 3 - thoat \n Nhap so: ");
        
        // Nhap he (Dai hoc hoac Cao dang)
        Scanner inp=new Scanner(System.in);
        int chonHe;
        do{
            chonHe=inp.nextInt();
            if(chonHe!=1 && chonHe!=2&&chonHe!=3)
             System.out.print("\n Chon he chua dung!");
        }while(chonHe!=1 && chonHe!=2&&chonHe!=3);
        
        // Nhap so sinh vien
        
        System.out.print("\n Nhap so sinh vien \n n= ");
        int n;
        do{
            n=inp.nextInt();
            if(n<3 && n>30)
             System.out.print("\n Nhap lai so sinh vien!");
        }while(n<3 && n>30);
        
        String hoTen, diaChi, he;
        int namSinh; 
        float d1, d2, d3, d4,d5;
                
        switch (chonHe){
            
            // SINH VIEN CAO DANG
            case 2:
            {
                
               
                for (int i=0;i<n;i++){
                    System.out.print("\n Nhap thong tin cho sv thu"+(i+1));
                    System.out.print("\n + Ho va ten: ");
                    hoTen = inp.next();
                    System.out.print("\n + Dia chi: ");
                    diaChi = inp.next();
                    he = "Cao dang";
                    System.out.print("\n + Nam sinh: ");
                    namSinh = inp.nextInt();
                    do{
                        System.out.print("\n + Diem 1: ");
                        d1 =inp.nextFloat();
                        if(d1<0&&d1>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d1<0&&d1>10);
                    
                    do{
                        System.out.print("\n + Diem 2: ");
                        d2 =inp.nextFloat();
                        if(d2<0&&d2>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d2<0&&d2>10);
                    
                    do{
                        System.out.print("\n + Diem 3: ");
                        d3 =inp.nextFloat();
                        if(d3<0&&d3>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d3<0&&d3>10);
                    
                    do{
                        System.out.print("\n + Diem 4: ");
                        d4 =inp.nextFloat();
                        if(d4<0&&d4>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d4<0&&d4>10);
                    
                     // khoi tao mang doi tuong
                    a[i] = new SVCD(hoTen,diaChi, he,namSinh,d1,d2,d3,d4);
                   
                    
                }
                
                 // in danh sach sinh vien co diem chu A
                System.out.print("\n * IN DANH SACH SV CO DIEM CHU LA A: \n");
                 for(int i=0;i<n;i++)
                    if(a[i].DiemChu()=='A')
                        a[i].InKQ();
                  // Doi ten sinh vien sang chu in hoa
                  System.out.print("\n * IN TEN SINH VIEN DA DOI THANH CHU HOA \n");
                  for(int i=0;i<n;i++){
                   a[i].hoTen = a[i].hoTen.toUpperCase();
                   System.out.print("\n" + a[i].hoTen);
                   
                  }
            }
            
            // SINH VIEN DAI HOC
            case 1:
            {
                for (int i=0;i<n;i++){
                    System.out.print("\n Nhap thong tin cho sv thu"+(i+1));
                    System.out.print("\n + Ho va ten: ");
                    hoTen = inp.next();
                    System.out.print("\n + Dia chi: ");
                    diaChi = inp.next();
                    he = "Dai hoc";
                    System.out.print("\n + Nam sinh: ");
                    namSinh = inp.nextInt();
                    do{
                        System.out.print("\n + Diem 1: ");
                        d1 =inp.nextFloat();
                        if(d1<0&&d1>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d1<0&&d1>10);
                    
                    do{
                        System.out.print("\n + Diem 2: ");
                        d2 =inp.nextFloat();
                        if(d2<0&&d2>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d2<0&&d2>10);
                    
                    do{
                        System.out.print("\n + Diem 3: ");
                        d3 =inp.nextFloat();
                        if(d3<0&&d3>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d3<0&&d3>10);
                    
                    do{
                        System.out.print("\n + Diem 4: ");
                        d4 =inp.nextFloat();
                        if(d4<0&&d4>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d4<0&&d4>10);
                    
                    do{
                        System.out.print("\n + Diem 5: ");
                        d5 =inp.nextFloat();
                        if(d5<0&&d5>10)
                            System.out.print("\n Nhap lai diem! ");
                    }while(d5<0&&d5>10);
                    
                     // khoi tao mang doi tuong
                    a[i] = new SVDH(hoTen,diaChi, he,namSinh,d1,d2,d3,d4,d5);
                   
                    
                }
               
                 // in danh sach sinh vien co diem chu A
                System.out.print("\n * IN DANH SACH SV CO DIEM CHU LA A: \n");
                 for(int i=0;i<n;i++)
                    if(a[i].DiemChu()=='A')
                        a[i].InKQ();
                 // Doi ten sinh vien sang chu in hoa
                  System.out.print("\n * IN TEN SINH VIEN DA DOI THANH CHU HOA \n");
                  for(int i=0;i<n;i++){
                   a[i].hoTen = a[i].hoTen.toUpperCase();
                   System.out.print("\n" + a[i].hoTen);
                   
                  }
                 
            }
                 default :
                System.out.print("\n Ket thuc ");
        }
        
        
    }
    

}

[ Lập trình mạng với Java ] Lập trình SOCKET kết nôi Client - Server để tính tổng 2 số

in , , , , /

Lập trình SOCKET kết nôi Client - Server để tính tổng 2 số

/* 
 Viết chương trình:
  - Client: Nhập vào từ bàn phím 2 số nguyên (a,b). Client chờ nhận kết quả từ Server để in ra màn hình
 - Server: Nhận 2 số nguyên mà Client vừa gửi, tính tổng của chúng và gửi kết quả cho Client
*/ 

 //----------CLIENT----------------------------------------
import java.net.UnknownHostException; 
import java.io.DataInputStream; 
import java.io.DataOutputStream; 
import java.io.IOException; 
import java.net.Socket; 


 public class Socket_tong2so_client {

     public static void main(String []args) throws IOException 
    { 
        System.out.println("Client dang ket noi voi Server... "); 
        String a,b,tong; 

         //tao socket de ket noi toi server, Locallhost: server mặc định 
        Socket ClientSocket = new Socket("Localhost", 1234); 

         //thong bao da ket noi thanh cong 
        System.out.println("Da ket noi voi Server! "); 

         //tao luong nhap du lieu tu ban phim 
        DataInputStream inFromUser = new DataInputStream(System.in); 

         //tao luong nhan du lieu tu server 
        DataInputStream inFromServer = new DataInputStream(ClientSocket.getInputStream()); 

         //tao luong gui du lieu len server 
        DataOutputStream outToServer = new DataOutputStream(ClientSocket.getOutputStream()); 

         // nhap du lieu tu ban phim
        try{ 
            System.out.println("\n Nhap a :"); 
            a=inFromUser.readLine(); 
            System.out.println("\n Nhap b :"); 
             b=inFromUser.readLine(); 

             // gui len server 
             outToServer.writeBytes(a+'\n'); 
            outToServer.writeBytes(b+'\n'); 
        }catch(UnknownHostException e) 
        { 
            System.err.println("Server Not Found"); 
            System.exit(1); 
        }catch(IOException e) 
        { 
            System.err.println("Cannot make a connection"); 
            System.exit(1); 
        } 
         
        //nhan ve tu server 
        tong=inFromServer.readLine(); 

         //in ra man hinh 
        System.out.println("\n Ket qua :"+tong); 

         //dong luong gui du lieu len server 
        outToServer.close(); 

         //dong luong nhan du lieu tu server 
        inFromServer.close(); 

         //dong socket client 
        ClientSocket.close(); 
    } 

 } 

 //----------SERVER----------------------------------------


import java.io.DataInputStream; 
import java.io.DataOutputStream; 
import java.io.IOException; 
import java.net.ServerSocket; 
import java.net.Socket; 

 public class Socket_tong2so_server {
    public static void main(String []args) throws IOException 
    { 
        System.out.println("Server dang khoi dong... "); 
        String so1,so2,so3; 
        int tong; 

         // tao server socket 
        ServerSocket server = new ServerSocket(1234); 
        System.out.println("Server da san sang! "); 

         //tao 1 socket do ket noi tu client toi server 
        Socket connectionSocket = server.accept(); 

         //tao luong nhan du lieu tu client 
        DataInputStream inFromClient = new DataInputStream(connectionSocket.getInputStream()); 

         // tao luong gui du lieu toi client 
        DataOutputStream outToClient = new DataOutputStream(connectionSocket.getOutputStream()); 

         // truyen du lieu tu client vao 2 bien so1 va so2 
        so1 = inFromClient.readLine(); 
        so2 = inFromClient.readLine(); 

         //ep so1 va so2 tu kieu String sang kieu Integer 
        int a = Integer.parseInt(so1); 
        int b = Integer.parseInt(so2); 

         //tinh tong a + b 
        tong = a + b; 

         //ep tong  sang kieu String 
        so3 = String.valueOf(tong); 

         //gui so3 ve client 
        outToClient.writeBytes(so3+'\n'); 

         //dong luong nhan du lieu tu client 
        inFromClient.close(); 

         //dong luong gui du lieu ve client 
        outToClient.close(); 

         //dong server socket 
        server.close(); 
    } 

 } 

 /* 
Chú ý: Run class Server trước sau đó Run class Client
*/
 

Chúc các bạn thành công!

 
[Tham khao: Internet]

Subscribe to: Posts (Atom)