论文拾萃|用子集和、集合覆盖及遗传算法解决可变尺寸装箱（VSBPP）问题（JAVA）

private ArrayList<Item> solveSSP(int i, ArrayList<Item> unpacked_itemsJ_, double[] maximum_load_z) {    ArrayList<Item> selected_items_at_this_iteration = new ArrayList<>();    try {        IloCplex cplex = new IloCplex();        cplex.setOut(null); //turn off display        IloLinearNumExpr obj = cplex.linearNumExpr();        String[] var_names = new String[unpacked_itemsJ_.size()];        for (int j = 0; j < var_names.length; j++) {            var_names[j] = "x" + unpacked_itemsJ_.get(j).index;        }        IloNumVar[] x = cplex.boolVarArray(unpacked_itemsJ_.size(), var_names);        for (int j = 0; j < x.length; j++) {            obj.addTerm(data.item_weights_w[unpacked_itemsJ_.get(j).index], x[j]);        }        cplex.addMaximize(obj);        //subject to (2)        IloLinearNumExpr expr = cplex.linearNumExpr();        for (int j = 0; j < x.length; j++) {            expr.addTerm(data.item_weights_w[unpacked_itemsJ_.get(j).index], x[j]);        }        cplex.addLe(expr, data.bin_capacicty_W[i]);        if (cplex.solve()) {            maximum_load_z[i] = cplex.getObjValue();            for (int j = 0; j < x.length; j++) {                if (cplex.getValue(x[j]) > 0.995) {                    selected_items_at_this_iteration.add(unpacked_itemsJ_.get(j));                }            }        } else {            System.err.println("Failed to solve SSP for bin " + i);            System.exit(-1);        }        cplex.clearModel();        cplex.endModel();        cplex.end();    } catch (IloException e) {        e.printStackTrace();    }    return selected_items_at_this_iteration;}

  private void SSP1() {        System.out.println("Starting SSP1.");        //step 0: initialization        ArrayList<Item> unpacked_itemsJ_ = new ArrayList<>(data.item_num_n);        double[] maximum_load_z = new double[data.bin_num_m];        ArrayList<Bin> packed_bins = new ArrayList<>();        for (int i = 0; i < data.item_num_n; i++) {            unpacked_itemsJ_.add(new Item(i));        }        //iterate until the unpacked item set J_ is empty        while (!unpacked_itemsJ_.isEmpty()) {            HashMap<Integer, ArrayList<Item>> selected_items_S = new HashMap<>();            double minimal_ratio_i = Double.POSITIVE_INFINITY;            int winner_index = -1;            //step 1: compute maximum_load_z and selected_items_S for each bin            for (int i = 0; i < data.bin_num_m; i++) {                maximum_load_z[i] = 0.0000000001;                selected_items_S.put(i,                        solveSSP(i, unpacked_itemsJ_,maximum_load_z));                if(maximum_load_z[i] == 0.0) maximum_load_z[i] = 0.0000000001;                double ratio = data.bin_cost_C[i] / maximum_load_z[i];                //step 2: compute minimal ratio i*                if (ratio < minimal_ratio_i) {                    minimal_ratio_i = ratio;                    winner_index = i;                }            }            //step 3: load the items of i* into the bin at winner_index            packed_bins.add(new Bin(winner_index, selected_items_S.get(winner_index)));            //step 4: remove the packed items from the unpacked item set J_            for (Item item : selected_items_S.get(winner_index)) {                unpacked_itemsJ_.remove(item);            }        }        //store solutions        //the first solution is #0        Solution solution = new Solution(solution_counter, packed_bins);        solutions.add(solution);        solutions_GA.add(solution);//        System.out.println(solutions.get(solution_counter));    }

private void SSP2() {        System.out.println("Starting SSP2.");        //step 0: initialization        ArrayList<Item> unpacked_itemsJ_ = new ArrayList<>(data.item_num_n);        double[] maximum_load_z = new double[data.bin_num_m];        ArrayList<Bin> packed_bins = new ArrayList<>();        for (int i = 0; i < data.item_num_n; i++) {            unpacked_itemsJ_.add(new Item(i));        }        //iterate until the unpacked item set J_ is empty        while (!unpacked_itemsJ_.isEmpty()) {            HashMap<Integer, ArrayList<Item>> selected_items_S = new HashMap<>();            double minimal_ratio_i = Double.POSITIVE_INFINITY;            int winner_index = -1;            //only those bins that can include the largest unpacked items are considered            double max_weight = Double.NEGATIVE_INFINITY;            for (Item item : unpacked_itemsJ_) {                double weight = item.weight;                if (weight > max_weight) max_weight = weight;            }            //step 1: compute maximum_load_z and selected_items_S for each bin            for (int i = 0; i < data.bin_num_m; i++) {                maximum_load_z[i] = 0.0000000001;                if (data.bin_capacicty_W[i] < max_weight) continue;                selected_items_S.put(i,                        solveSSP(i, unpacked_itemsJ_,maximum_load_z));                if(maximum_load_z[i] == 0.0) maximum_load_z[i] = 0.0000000001;                double ratio = data.bin_cost_C[i] / maximum_load_z[i];                //step 2: compute minimal ratio i*                if (ratio < minimal_ratio_i) {                    minimal_ratio_i = ratio;                    winner_index = i;                }            }            //step 3: load the items of i* into the bin at winner_index            packed_bins.add(new Bin(winner_index, selected_items_S.get(winner_index)));            //step 4: remove the packed items from the unpacked item set J_            for (Item item : selected_items_S.get(winner_index)) {                unpacked_itemsJ_.remove(item);            }        }        //store solutions        solution_counter++;        Solution solution = new Solution(solution_counter, packed_bins);        solutions.add(solution);        solutions_GA.add(solution);//        System.out.println(solutions.get(solution_counter));    }

  private void SSP3() {        System.out.println("Starting SSP3.");        //step 0: initialization        HashMap<Integer, Item> unpacked_itemsJ_ = new HashMap<>(data.item_num_n);        double[] maximum_load_z = new double[data.bin_num_m];        ArrayList<Bin> packed_bins = new ArrayList<>();        for (int i = 0; i < data.item_num_n; i++) {            unpacked_itemsJ_.put(i, new Item(i));        }        //iterate until the unpacked item set J_ is empty        while (!unpacked_itemsJ_.isEmpty()) {            HashMap<Integer, ArrayList<Item>> selected_items_S = new HashMap<>();            double minimal_ratio_i = Double.POSITIVE_INFINITY;            int winner_index = -1;            //only those bins that can include the largest unpacked items are considered            //at each iteration the largest unpacked item is forced to be included in the set of items            //that are packed into the selected bin            double max_weight = Double.NEGATIVE_INFINITY;            int heaviest_item_index = -1;            for (Item item : unpacked_itemsJ_.values()) {                double weight = item.weight;                if (weight > max_weight) {                    max_weight = weight;                    heaviest_item_index = item.index;                }            }            //step 1: compute maximum_load_z and selected_items_S for each bin            for (int i = 0; i < data.bin_num_m; i++) {                maximum_load_z[i] = 0.00000000001;                if (data.bin_capacicty_W[i] < max_weight) continue;                selected_items_S.put(i,                        solveSSP3(i, heaviest_item_index, max_weight, unpacked_itemsJ_,maximum_load_z));                if(maximum_load_z[i] == 0.0) maximum_load_z[i] = 0.0000000001;                double ratio = data.bin_cost_C[i] / maximum_load_z[i];                //step 2: compute minimal ratio i*                if (ratio < minimal_ratio_i) {                    minimal_ratio_i = ratio;                    winner_index = i;                }            }            //step 3: load the items of i* into the bin at winner_index            packed_bins.add(new Bin(winner_index, selected_items_S.get(winner_index)));            //step 4: remove the packed items from the unpacked item set J_            for (Item item : selected_items_S.get(winner_index)) {                unpacked_itemsJ_.remove(item.index);            }        }        //store solutions        solution_counter++;        Solution solution = new Solution(solution_counter, packed_bins);        solutions.add(solution);        solutions_GA.add(solution);//        System.out.println(solutions.get(solution_counter));    }

/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释 
* private void SSP4() {        System.out.println("Starting SSP4.");        ArrayList<ArrayList<Bin>> each_bin_packing = new ArrayList<>(data.bin_num_m);        for (int i = 0; i < data.bin_num_m; i++) {            //0: set J_ to J (all items are unpacked)            ArrayList<Item> unpacked_itemsJ_ = new ArrayList<>(data.item_num_n);            //store a solution at this iteration            ArrayList<Bin> packed_bins = new ArrayList<>();            for (int j = 0; j < data.item_num_n; j++) {                unpacked_itemsJ_.add(new Item(j, data.item_weights_w[j]));            }            int k = i;            boolean isJEmpty = false;            //step 1:            while (!isJEmpty) {                ArrayList<Bin> packed_bins_at_this_iteration = new ArrayList<>();                //set Jk - items that can be packed into bin of type k                ArrayList<Item> items_fit_for_bin_Jk = new ArrayList<>();                for (Item item : unpacked_itemsJ_) {                    if (item.weight <= data.bin_capacicty_W[k]) {                        items_fit_for_bin_Jk.add(item);                    }                }                //store items in non-increasing order                Queue<Item> itemQueue = new PriorityQueue<>(Collections.reverseOrder());                for (Item item : items_fit_for_bin_Jk) {                    itemQueue.offer(item);                }                //step 2: load items of maximum weight not exceeding the capacity                while (!itemQueue.isEmpty()) {                    double total_weight = 0;                    ArrayList<Item> selected_items_at_this_iteration = new ArrayList<>();                    boolean canPackMore = true;                    while (canPackMore) {                        Item item = itemQueue.poll();                        total_weight += item.weight;                        selected_items_at_this_iteration.add(item);                        if (itemQueue.size() >= 1) {                            Item next = itemQueue.peek();                            if (total_weight + next.weight > data.bin_capacicty_W[k]) canPackMore = false;                        } else canPackMore = false;                    }                    packed_bins_at_this_iteration.add(new Bin(k, selected_items_at_this_iteration));                }                //step 3: assign to each bin the smallest feasible capacity                if (k != 0) { //if k'th bin is 0, then there does not exist a smaller feasible packing                    for (Bin bin : packed_bins_at_this_iteration) {                        ArrayList<Item> items = bin.selected_items;                        double total_weight = 0;                        for (Item item : items) {                            total_weight += item.weight;                        }                        int smallest_bin_index = k;                        for (int j = data.bin_num_m - 1; j > -1; j--) {                            if (j == k) continue; //no need to check for the same bin                            if (total_weight > data.bin_capacicty_W[j]) break; //a smaller bin can not be found                            else smallest_bin_index = j;                        }                        //check if smallest bin index has been updated                        if (smallest_bin_index != k) bin.setBinIndex(smallest_bin_index);                    }                }                //step 4: update the unpacked item set                for (Bin bin : packed_bins_at_this_iteration) {                    for (Item item : bin.selected_items) {                        unpacked_itemsJ_.remove(item);                    }                }                //step 5: test if the set is empty                if (!unpacked_itemsJ_.isEmpty()) {                    k++;                    isJEmpty = false; //go to step 1                } else {                    isJEmpty = true; //go to step 6                }                for(Bin bin : packed_bins_at_this_iteration){                    packed_bins.add(bin);                }            }            //step 6: store the obtained solution            each_bin_packing.add(packed_bins);        }        //select least cost packing from the set each_bin_packing        double[] costs = new double[data.bin_num_m];        for (int i = 0; i < each_bin_packing.size(); i++) {            double total_cost = 0;            for (Bin bin : each_bin_packing.get(i)) {                total_cost += bin.bin_cost;            }            costs[i] = total_cost;        }        double least_cost = Double.POSITIVE_INFINITY;        int least_cost_bin_index = -1;        for (int i = 0; i < costs.length; i++) {            if (costs[i] < least_cost) {                least_cost = costs[i];                least_cost_bin_index = i;            }        }        //store the best obtained solution        solution_counter++;        Solution solution = new Solution(solution_counter, each_bin_packing.get(least_cost_bin_index));        solutions.add(solution);        solutions_GA.add(solution);//        System.out.println(solutions.get(solution_counter));    }
*/

/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释 
* private void probabilisticHeuristic() {        System.out.println("Starting Probabilistic Heuristic.");        for (int z = 0; z < iter; z++) {            ArrayList<ArrayList<Bin>> each_bin_packing = new ArrayList<>(data.bin_num_m);            for (int i = 0; i < data.bin_num_m; i++) {                //0: set J_ to J (all items are unpacked)                ArrayList<Item> unpacked_itemsJ_ = new ArrayList<>(data.item_num_n);                //store a solution at this iteration                ArrayList<Bin> packed_bins = new ArrayList<>();                for (int j = 0; j < data.item_num_n; j++) {                    unpacked_itemsJ_.add(new Item(j));                }                int k = i;                boolean isJEmpty = false;                //step 1:                while (!isJEmpty) {                    ArrayList<Bin> packed_bins_at_this_iteration = new ArrayList<>();                    //set Jk - items that can be packed into a bin of type k                    ArrayList<Item> items_fit_for_bin_Jk = new ArrayList<>();                    for (Item item : unpacked_itemsJ_) {                        if (item.weight <= data.bin_capacicty_W[k]) {                            items_fit_for_bin_Jk.add(item);                        }                    }                    //store items in non-increasing order                    Queue<Item> itemQueue = new PriorityQueue<>(Collections.reverseOrder());                    for (Item item : items_fit_for_bin_Jk) {                        itemQueue.offer(item);                    }                    ArrayList<Item> selected_items_at_this_iteration = new ArrayList<>();                    double total_weight = 0;                    //step 2: one item is randomly selected out of the two heaviest unpacked items                    //and is assigned to the first bin where it fits (or else into an empty bin)                    while (!itemQueue.isEmpty()) {                        boolean canPackMore = true;                        Item selected_item = null;                        while (canPackMore) {                            Item item1 = itemQueue.poll();                            Item item2 = null;                            selected_item = item1;                            if (itemQueue.size() >= 1) {                                double random = ThreadLocalRandom.current().nextDouble(0, 101.0);                                //select item 2 if random > 0.5                                if (random > 0.50) {                                    item2 = itemQueue.poll();                                    selected_item = item2;                                    itemQueue.offer(item1);                                }                            }                            total_weight += selected_item.weight;                            if (total_weight > data.bin_capacicty_W[k]) {                                canPackMore = false;                                //pack the previously selected items into a bin                                packed_bins_at_this_iteration.add(new Bin(k, selected_items_at_this_iteration));                                //selected item that does not fit goes to the next empty bin                                selected_items_at_this_iteration = new ArrayList<>();                                selected_items_at_this_iteration.add(selected_item);                                total_weight = selected_item.weight;                            } else {                                selected_items_at_this_iteration.add(selected_item);                            }                            if (itemQueue.isEmpty()) {                                canPackMore = false;                                packed_bins_at_this_iteration.add(new Bin(k, selected_items_at_this_iteration));                            }                        }                    }                    //step 3: assign to each bin the smallest feasible capacity                    if (k != 0) { //if k'th bin is 0, then there does not exist a smaller feasible packing                        for (Bin bin : packed_bins_at_this_iteration) {                            ArrayList<Item> items = bin.selected_items;                            total_weight = 0;                            for (Item item : items) {                                total_weight += item.weight;                            }                            int smallest_bin_index = k;                            for (int j = data.bin_num_m - 1; j > -1; j--) {                                if (j == k) continue; //no need to check for the same bin                                if (total_weight > data.bin_capacicty_W[j]) break; //a smaller bin can not be found                                else smallest_bin_index = j;                            }                            //check if smallest bin index has been updated                            if (smallest_bin_index != k) bin.setBinIndex(smallest_bin_index);                        }                    }                    //step 4: update the unpacked item set                    for (Bin bin : packed_bins_at_this_iteration) {                        for (Item item : bin.selected_items) {                            unpacked_itemsJ_.remove(item);                        }                    }                    //step 5: test if the set is empty                    if (!unpacked_itemsJ_.isEmpty()) {                        k++;                        isJEmpty = false; //go to step 1                    } else {                        isJEmpty = true; //go to step 6                    }                    for(Bin bin : packed_bins_at_this_iteration){                        packed_bins.add(bin);                    }                }                //step 6: store the obtained solution                each_bin_packing.add(packed_bins);            }            //store the best obtained solutions            for (int i = 0; i < each_bin_packing.size(); i++) {                solution_counter++;                solutions.add(new Solution(solution_counter, each_bin_packing.get(i)));//                System.out.println(solutions.get(solution_counter));            }        }    }
*/

private void twoPhaseHeuristic() {//        generateNewVectors();        generateHashVectors();        setCoveringProblem();    }private void generateHashVectors() {    HashMap<ArrayList<Double>,Bin> label_hashMap = new HashMap<>();    for(Solution solution : solutions){        for(Bin bin : solution.bins){            ArrayList<Double> labels = new ArrayList<>();            double[] label = bin.getLabel();//label是每个bin的标识值，相等就认为是同一个            for(Double d : label) labels.add(d);            label_hashMap.put(labels,bin);//这步就是在去重        }    }    for(Bin bin : label_hashMap.values()){        bin.addIncidence();//使标识item出现的数组的对应位为1    }    //force the best solution columns to be included in the incidence matrix    for(Bin bin : solutions.get(best_initial_solution_index).bins){        bin.addIncidence();    }}private void setCoveringProblem() {        try {            IloCplex cplex = new IloCplex();            IloLinearNumExpr obj = cplex.linearNumExpr();            for(Solution solution : solutions){                int uniqueID = 1;                for(Bin bin : solution.bins){                    bin.setVar(cplex, solution.solutionID,uniqueID);                    uniqueID++;                }            }            for(Solution solution : solutions){                for(Bin bin : solution.bins){                    obj.addTerm(bin.bin_cost,bin.getVar());                }            }            cplex.addMinimize(obj);            //subject to (8)            for (int j = 0; j < data.item_num_n; j++) {                IloLinearNumExpr expr = cplex.linearNumExpr();                for(Solution solution : solutions){                    for(Bin bin : solution.bins){                        for(Item item : bin.selected_items){                            if(item.index == j){                                expr.addTerm(bin.getIncidence()[item.index],bin.getVar());                            }                        }                    }                }                cplex.addEq(expr,1.0,"Item"+j);//                cplex.addGe(expr,1.0);//TODO: Ge sometimes produces infeasible solutions            }            cplex.setParam(IloCplex.DoubleParam.TiLim,T_max);            cplex.setOut(null); //turn off display            if(cplex.solve()){                ArrayList<Bin> selected_bins = new ArrayList<>();                for(Solution solution : solutions){                    for(Bin bin : solution.bins){                        if(cplex.getValue(bin.getVar()) > 0.995){                            selected_bins.add(bin);                        }                    }                }                Solution solution_SCP = new Solution(solution_counter++,selected_bins);                System.out.println(solution_SCP);                this.best_cost_cplex = cplex.getObjValue();                System.out.println("SCP Total Cost: " + best_cost_cplex);                System.out.println("vs");                System.out.println("Initial cost : " + solutions.get(best_initial_solution_index).calculateCost());            } else {                System.err.println("Failed to solve the Set-Covering Problem!");            }//            String output_path = "out" + File.separator + "SCP";//            if (!Files.exists(Path.of(output_path))) {//                try {//                    Files.createDirectory(Path.of(output_path));//                } catch (IOException e) {//                    e.printStackTrace();//                }//            }//            cplex.writeSolution(output_path + File.separator + "SCP"+"_sol.txt");//            cplex.exportModel(output_path + File.separator + "SCP"+"_model.lp");            cplex.clearModel();            cplex.endModel();            cplex.end();        } catch (IloException e) {            e.printStackTrace();        }    }}

public class Chromosome {    public ArrayList<Item> items = new ArrayList<>();    public double fitness;    public int solution_index;//后面方法比较多，我就不贴了

/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释 
* private Chromosome crossover(Chromosome parent1, Chromosome parent2, double random) {    Chromosome child = new Chromosome();    HashMap<Integer, Item> child_items_HashMap = new HashMap<>();    HashMap<Integer, Item> child_items_ordered_HashMap = new HashMap<>();    ArrayList<Item> child_items_resultant_list = new ArrayList<>();    if(random > 0.7){        //similar-job-one-point crossover        int point = ThreadLocalRandom.current().nextInt(0, data.item_num_n);        ArrayList<Item> parent1_items = parent1.getItems();        ArrayList<Item> parent2_items = parent2.getItems();        child_items_HashMap = new HashMap<>();        child_items_ordered_HashMap = new HashMap<>();        //copy the identical items        for (int i = 0; i < data.item_num_n; i++) {            Item parent1_item = parent1_items.get(i);            Item parent2_item = parent2_items.get(i);            if(parent1_item.index == parent2_item.index                    && !child_items_HashMap.containsKey(parent1_item.index)){                child_items_HashMap.put(parent1_item.index, parent1_item);                child_items_ordered_HashMap.put(i,parent1_item);            }        }        int counter1 = 0;        //copy parent1 items before the point        for (int i = 0; i < point; i++) {            Item parent1_item = parent1_items.get(counter1);            if(!child_items_HashMap.containsKey(parent1_item.index)){                if(!child_items_ordered_HashMap.containsKey(i)){                    child_items_HashMap.put(parent1_item.index, parent1_item);                    child_items_ordered_HashMap.put(i,parent1_item);                    counter1++;                } else continue; //i++, while keeping counter at the same place            } else {                i--;                counter1++;            }        }        int counter2 = 0;        //copy parent2 items after the point        for (int i = point; i < data.item_num_n; i++) {            Item parent2_item = parent2_items.get(counter2);            if (!child_items_HashMap.containsKey(parent2_item.index)){                if(!child_items_ordered_HashMap.containsKey(i)){                    child_items_HashMap.put(parent2_item.index, parent2_item);                    child_items_ordered_HashMap.put(i,parent2_item);                    counter2++;                } else continue; //i++, while keeping counter at the same place            } else {                i--;                counter2++;            }        }    }    else if (random > 0.4) {        //three-point crossover        int point1 = ThreadLocalRandom.current().nextInt(0, data.item_num_n - 2);        //ensures that point2 is greater than point1        int point2 = ThreadLocalRandom.current().nextInt(point1 + 1, data.item_num_n - 1);        //ensures that point3 is greater than point2        int point3 = ThreadLocalRandom.current().nextInt(point2 + 1, data.item_num_n);        ArrayList<Item> parent1_items = parent1.getItems();        ArrayList<Item> parent2_items = parent2.getItems();        child_items_HashMap = new HashMap<>();        child_items_ordered_HashMap = new HashMap<>();        //the items outside point1 are copied into the offspring        for (int i = 0; i < point1; i++) {            child_items_HashMap.put(parent1_items.get(i).index, parent1_items.get(i));            child_items_ordered_HashMap.put(i, parent1_items.get(i));        }        for (int i = point2 + 1; i < point3; i++) {            child_items_HashMap.put(parent1_items.get(i).index, parent1_items.get(i));            child_items_ordered_HashMap.put(i, parent1_items.get(i));        }        int counter = 0;        for (int i = point1; i <= point2; i++) {            Item parent2_item = parent2_items.get(counter);            //check if the child already contains parent2 item            if (child_items_HashMap.get(parent2_item.index) == null) {                child_items_HashMap.put(parent2_item.index, parent2_item);                child_items_ordered_HashMap.put(i, parent2_item);            } else {                i--;            }            counter++;        }        for (int i = point3; i < data.item_num_n; i++) {            Item parent2_item = parent2_items.get(counter);            //check if the child already contains parent2 item            if (child_items_HashMap.get(parent2_item.index) == null) {                child_items_HashMap.put(parent2_item.index, parent2_item);                child_items_ordered_HashMap.put(i, parent2_item);            } else {                i--;            }            counter++;        }    } else {        //two-point crossover        int point1 = ThreadLocalRandom.current().nextInt(0, data.item_num_n - 1);        //ensures that point2 is greater than point1        int point2 = ThreadLocalRandom.current().nextInt(point1 + 1, data.item_num_n);        ArrayList<Item> parent1_items = parent1.getItems();        ArrayList<Item> parent2_items = parent2.getItems();        child_items_HashMap = new HashMap<>();        child_items_ordered_HashMap = new HashMap<>();        //the items outside the selected two points are copied into the offspring        for (int i = 0; i < point1; i++) {            child_items_HashMap.put(parent1_items.get(i).index, parent1_items.get(i));            child_items_ordered_HashMap.put(i, parent1_items.get(i));        }        for (int i = (point2 + 1); i < data.item_num_n; i++) {            child_items_HashMap.put(parent1_items.get(i).index, parent1_items.get(i));            child_items_ordered_HashMap.put(i, parent1_items.get(i));        }        int counter = 0;        for (int i = point1; i <= point2; i++) {            Item parent2_item = parent2_items.get(counter);            //check if the child already contains parent2 item            if (child_items_HashMap.get(parent2_item.index) == null) {                child_items_HashMap.put(parent2_item.index, parent2_item);                child_items_ordered_HashMap.put(i, parent2_item);            } else {                i--;            }            counter++;        }    }    //---------------------------------    child_items_resultant_list = new ArrayList<>();    for (int i = 0; i < data.item_num_n; i++) {        child_items_resultant_list.add(child_items_ordered_HashMap.get(i));    }
*/
    //add the dummy node    child_items_resultant_list.add(data.item_num_n, new Item(data.item_num_n, 0));    HashMap<Integer, Item> duplicateChecker = new HashMap<>();    for (Item item : child_items_resultant_list) {        duplicateChecker.put(item.index, item);    }    if (duplicateChecker.size() < data.item_num_n + 1)        System.err.println("Error! Item number is wrong in crossover().");    child.addItems(child_items_resultant_list);    return child;}

/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释 
* private void mutate(Chromosome chromosome) {        boolean improved_solution = false;        //solution index obtained after solving shortest path problem        Solution solution = solutions.get(chromosome.getSolution_index());        //compute the ratio of the cost to the actual load for each bin        //sort bins in decreasing order        Queue<Bin> binQueue = new PriorityQueue<>(Collections.reverseOrder());        HashMap<Integer, Item> remaining_items = new HashMap<>();        for(Bin bin : solution.bins){            double load = 0;            for(Item item : bin.selected_items){                load += item.weight;                remaining_items.put(item.index,item);            }            bin.setRatio_GA(bin.bin_cost / load);            binQueue.offer(bin);        }        HashMap<Integer, Item> items_selected_subset_J_ = new HashMap<>();        ArrayList<Bin> selected_bins = new ArrayList<>();        double original_cost_total = 0;        int k = 0;        //stop when cardinality exceeds the preset upper bound k        while(k < parameters.item_UB_k){            Bin bin = binQueue.poll();            for(Item item : bin.selected_items){                items_selected_subset_J_.put(item.index,item);                remaining_items.remove(item.index);            }            original_cost_total += bin.bin_cost;            k = items_selected_subset_J_.size();            selected_bins.add(bin);        }        double best_cost = original_cost_total;        HashMap<Integer, Item> unpacked_itemsJ_ = new HashMap<>();        for(Item item : items_selected_subset_J_.values()){            unpacked_itemsJ_.put(item.index,item);        }        ArrayList<Bin> bins_SSP3 = new ArrayList<>();        //invoke SSP3 to solve a restricted VSBPP        bins_SSP3 = mutate(unpacked_itemsJ_);//这里的mutate是下面的方法//        bins_SSP3 = mutateSSP4(unpacked_itemsJ_);        double cost_ssp3 = 0;        for(Bin bin : bins_SSP3){            cost_ssp3 += bin.bin_cost;        }        if(cost_ssp3 < best_cost){//                System.out.println("Mutation produced a better cost!");            best_cost = cost_ssp3;            //replace the selected bins by a new solution            selected_bins.clear();            selected_bins.addAll(bins_SSP3);            improved_solution = true;        }        items_selected_subset_J_.clear();        //replacement of the mutated chromosome        if(improved_solution){            ArrayList<Item> items = new ArrayList<>();            for(Bin bin : selected_bins){                items.addAll(bin.selected_items);            }            items.addAll(remaining_items.values());            chromosome.clearItems();            chromosome.setFitness(0);            chromosome.setSolution_index(-1);            chromosome.addItems(items);            chromosome.addItems(new Item(data.item_num_n, 0)); //dummy node        }    }private ArrayList<Bin> mutate(HashMap<Integer, Item> given_item_set) {    //step 0: initialization    HashMap<Integer, Item> unpacked_itemsJ_ = new HashMap<>();    double[] maximum_load_z = new double[data.bin_num_m];    ArrayList<Bin> packed_bins = new ArrayList<>();    for(Item item : given_item_set.values()) unpacked_itemsJ_.put(item.index, item);    //iterate until the unpacked item set J_ is empty    while (!unpacked_itemsJ_.isEmpty()) {        HashMap<Integer, ArrayList<Item>> selected_items_S = new HashMap<>();        double minimal_ratio_i = Double.POSITIVE_INFINITY;        int winner_index = -1;        //only those bins that can include the largest unpacked items are considered        //at each iteration the largest unpacked item is forced to be included in the set of items        //that are packed into the selected bin        double max_weight = Double.NEGATIVE_INFINITY;        int heaviest_item_index = -1;        for (Item item : unpacked_itemsJ_.values()) {            double weight = item.weight;            if (weight > max_weight) {                max_weight = weight;                heaviest_item_index = item.index;            }        }        //step 1: compute maximum_load_z and selected_items_S for each bin        for (int i = 0; i < data.bin_num_m; i++) {            maximum_load_z[i] = 0.00000000001;            if (data.bin_capacicty_W[i] < max_weight) continue;            List<Integer> index_list = new ArrayList<>(unpacked_itemsJ_.size() - 1); //excluding the heaviest item            for (Item item : unpacked_itemsJ_.values()) {                int index = item.index;                if (index != heaviest_item_index) index_list.add(index);            }            Solver cplexSolver = new Solver(i,heaviest_item_index,max_weight,                    maximum_load_z,index_list,unpacked_itemsJ_,selected_items_S);            cplexSolver.run();            maximum_load_z = cplexSolver.getMaximum_load_z();            selected_items_S.put(i,cplexSolver.getSelected_items_at_this_iteration());            cplexSolver = null;            //----------------------------------            if(maximum_load_z[i] == 0.0) maximum_load_z[i] = 0.0000000001;            double ratio = data.bin_cost_C[i] / maximum_load_z[i];            //step 2: compute minimal ratio i*            if (ratio < minimal_ratio_i) {                minimal_ratio_i = ratio;                winner_index = i;            }        }        //step 3: load the items of i* into the bin at winner_index        packed_bins.add(new Bin(winner_index, selected_items_S.get(winner_index)));        //step 4: remove the packed items from the unpacked item set J_        for (Item item : selected_items_S.get(winner_index)) {            unpacked_itemsJ_.remove(item.index);        }    }    return packed_bins;}
*/