{"entities":{"Q2221588":{"pageid":2232331,"ns":120,"title":"Item:Q2221588","lastrevid":78330857,"modified":"2026-05-06T11:20:20Z","type":"item","id":"Q2221588","labels":{"en":{"language":"en","value":"A memetic algorithm for the max-cut problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7304367"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221588$25A55B25-958A-4C26-B5F1-2619F798BE15","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b0a49786fbf9bfe504cb9de81325cdafccebdb4c","datavalue":{"value":{"text":"A memetic algorithm for the max-cut problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2221588$E5ECE853-D61D-4B3A-8399-9C313BC811D5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"95d1e79bcf1c0cbec9fb3d073071ad3fb3a7822d","datavalue":{"value":"1453.68139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$E74F678B-FA67-4C52-B75C-EDD29BB77873","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dff431cc4e6c7c45a09c7559f6db83e7efac4330","datavalue":{"value":"10.1504/IJCSM.2015.067544","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$4EDDA9E9-A2D4-45A6-B947-9CBE34B7EE7D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5112ae3c3513db11ee18ea219759173a8a6b6ad","datavalue":{"value":{"entity-type":"item","numeric-id":306102,"id":"Q306102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221588$2E5C0291-B34B-4A35-ACED-C63CFB2E8458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"92c256b7883a5a6f631a3a4a2045705215a1ae25","datavalue":{"value":{"entity-type":"item","numeric-id":415859,"id":"Q415859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221588$89BFD276-36C9-4135-84EF-C546F8C52630","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f306f7a0701f0c426c5681c314795b1e314a5dc6","datavalue":{"value":{"entity-type":"item","numeric-id":391694,"id":"Q391694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221588$166BA457-A297-4C34-814C-FD8C91163E96","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de7d6a80765516b521ff8175534b49851be83f47","datavalue":{"value":{"time":"+2021-02-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2221588$13259855-1FFF-447D-8BA1-17914EAA46B2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44eb41103bd56e7e977a20922788e85f03b2d466","datavalue":{"value":"Summary: Given an undirected graph \\(G = (V, E)\\) with a set \\(V\\) of vertices, and a set \\(E\\) of edges with weights, the max-cut problem consists of partitioning all vertices into two independent sets such that the sum of the weights of the edges between different sets is maximised. The max-cut problem is an NP-hard problem. An efficient memetic algorithm is proposed in this paper for the problem. The proposed memetic algorithm uses a local search procedure and a new crossover operator based on the encoding characteristic of the max-cut problem to generate new offsprings. Then the algorithm uses a function, which takes into account both the solution quality and the diversity of population, to control the population updating. Experiments were performed on three sets of benchmark instances of size up to 10,000 vertices. Experiment results and comparisons demonstrate the effectiveness of the proposed algorithm in both solution quality and computational time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221588$94E07B9E-550A-4B61-AA14-C9522BE703DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$13A269E2-41EA-47DE-B70E-7F3396793BCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$850C4370-7CB5-41A2-8030-75D892D2655A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3804cc9e144948214a41669006fa93d4662c80b6","datavalue":{"value":"68W50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$85D0B8A8-6D70-47DC-8275-D13EC96F9D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$1F492EDF-1EC9-4597-8D04-D9EB2FBF932C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$54C9BAA6-BCED-4772-B2D2-2AC92C9DC034","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c7c9656cc8caf0a39d099f6e1a020598551775db","datavalue":{"value":"7304367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$569F569F-6374-4F7D-B93D-CDE6E588B249","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d665173dc81790294af37e94b0e9f3bf8df667fc","datavalue":{"value":"max-cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221588$41A26A87-1DC1-4ED4-8A7E-E63C993A03EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea1ff5a5e657abc0a392084b74b3342d23f2f4c9","datavalue":{"value":"local search","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221588$CA588E40-E726-41BD-A680-7EC4BAD157C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29ced55fb0dee564062735a8d967bae32d7ebd8c","datavalue":{"value":"memetic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221588$F7A736E6-271E-4231-84B4-0810FAD398A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e68f5e21359249d51d9afea4168e8113e65eca8","datavalue":{"value":"combinatorial optimisation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221588$9743879A-679E-4F6A-B174-FC4E1705028C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79c330ad057aa46d00506bab4fba4646342b17d7","datavalue":{"value":"computing science","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221588$36F890DA-D309-4A03-A047-B4615AFCA0EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36119251ccdc824c091d97011115b53649446494","datavalue":{"value":"memetics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221588$10BBCF50-450E-4036-A9E4-A0602E6CB22D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221588$79C906BE-85DB-4B6A-9719-258FCF989218","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"18981249dacd7a9bec9b8ea842cd9019ae5e0c98","datavalue":{"value":"https://doi.org/10.1504/ijcsm.2015.067544","type":"string"},"datatype":"url"},"type":"statement","id":"Q2221588$DE2D5F8F-76ED-4F8D-980D-02F88A323BDF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5951c8465f16276b87a061fff1a29e7676ea871","datavalue":{"value":"W2037966956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221588$689F44FA-56B3-4AA8-8EAE-40C6124C967D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b64106385e0aa16cb88018a2168f1c419e2ef305","datavalue":{"value":{"entity-type":"item","numeric-id":339560,"id":"Q339560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96f900b5ffc104f1c07d06c897b84268b466a604","datavalue":{"value":{"amount":"+0.8414252996444702","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2221588$976EC285-4AF0-4D7B-9A51-F038FD4777BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45c0bcd38a935f9c61f5001bc05c34e3154eb6d4","datavalue":{"value":{"entity-type":"item","numeric-id":2353470,"id":"Q2353470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd408ef0452486cff5639167864f477b385a79d6","datavalue":{"value":{"amount":"+0.8068220019340515","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2221588$9AFE9C12-9C44-4688-941C-F28145EB80BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227130aac6bac609e21f86b055da10dd3e536bca","datavalue":{"value":{"entity-type":"item","numeric-id":763098,"id":"Q763098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c111bd60680d319e4bf6d92b5c18c8c0208145a","datavalue":{"value":{"amount":"+0.7883477210998535","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2221588$50691B6D-0CCA-420D-9113-A92E86DEDF19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7585618a5f4bf6130d19ba75ba8724ac7019ede","datavalue":{"value":{"entity-type":"item","numeric-id":2901043,"id":"Q2901043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dc2e9330a5be6abf9019c1a3e165aa746e9e2d8","datavalue":{"value":{"amount":"+0.779296875","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2221588$E69D9B57-CAA9-4665-9705-50C9CA66CA4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52e6e5ab5e51e0c4da4a0793bb04dcb03589d232","datavalue":{"value":{"entity-type":"item","numeric-id":1043356,"id":"Q1043356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c45b2231027bc536932717e2705b48e8080d082","datavalue":{"value":{"amount":"+0.7771891355514526","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2221588$E4C6D416-A557-4634-ACD4-2CD7CD97F63D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A memetic algorithm for the max-cut problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_memetic_algorithm_for_the_max-cut_problem"}}}}}