Date: Sat, 13 Mar 2010 18:57:44 -0800 From: Charlie Kester <corky1951@comcast.net> To: FreeBSD-gnats-submit@FreeBSD.org Subject: ports/144725: [NEW PORT] sysutils/gaffitter: A bin packing utility that uses a genetic algorithm Message-ID: <20100314025746.DAA3D106564A@hub.freebsd.org> Resent-Message-ID: <201003140300.o2E30IZe098147@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
>Number: 144725 >Category: ports >Synopsis: [NEW PORT] sysutils/gaffitter: A bin packing utility that uses a genetic algorithm >Confidential: no >Severity: non-critical >Priority: low >Responsible: freebsd-ports-bugs >State: open >Quarter: >Keywords: >Date-Required: >Class: change-request >Submitter-Id: current-users >Arrival-Date: Sun Mar 14 03:00:17 UTC 2010 >Closed-Date: >Last-Modified: >Originator: Charlie Kester >Release: FreeBSD 8.0-STABLE i386 >Organization: >Environment: System: FreeBSD atom.local 8.0-STABLE FreeBSD 8.0-STABLE #0: Sat Feb 27 16:59:19 PST 2010 root@atom.local:/usr/obj/usr/src/sys/ATOM i386 >Description: Genetic Algorithm File Fitter, GAFFitter for short, is a tool based on a genetic algorithm (GA) that tries to fit a collection of items into as few as possible volumes of a specific size. For example, the items might be files/directories and the volumes might be CDs or DVDs. The task of arranging items in such manner that the number of required bins is minimized is called Bin Packing, a NP-hard combinatorial problem for which no deterministic polynomial-time algorithm is known. Using heuristics, such as GAs, it is usually possible to approximate -- and often reach -- the best solution for the problem within a reasonable time. WWW: http://gaffitter.sourceforge.net >How-To-Repeat: >Fix: --- gaffitter-0.6.0.shar begins here --- # This is a shell archive. Save it in a file, remove anything before # this line, and then unpack it by entering "sh file". Note, it may # create directories; files and directories will be owned by you and # have default permissions. # # This archive contains: # # gaffitter # gaffitter/distinfo # gaffitter/Makefile # gaffitter/files # gaffitter/files/gaffitter.1 # gaffitter/pkg-descr # echo c - gaffitter mkdir -p gaffitter > /dev/null 2>&1 echo x - gaffitter/distinfo sed 's/^X//' >gaffitter/distinfo << '35d9e193aace9b4f36a9b63beabd07b8' XMD5 (gaffitter-0.6.0.tar.bz2) = a4a0fa0b3eeeaf49624d2e1b78de3cff XSHA256 (gaffitter-0.6.0.tar.bz2) = 61236240942d0319fb1c0a7e3da8424ddad7fe5abc82c2e1e3f2a89ccc9fe275 XSIZE (gaffitter-0.6.0.tar.bz2) = 44433 35d9e193aace9b4f36a9b63beabd07b8 echo x - gaffitter/Makefile sed 's/^X//' >gaffitter/Makefile << '50e4320c645ec6fd5114d4f3ed476bc6' X# ex:ts=8 X# Ports collection makefile for: gaffitter X# Date created: 13 Mar 2010 X# Whom: corky1951@comcast.net X# X# $FreeBSD$ X# X XPORTNAME= gaffitter XPORTVERSION= 0.6.0 XCATEGORIES= sysutils XMASTER_SITES= SF/${PORTNAME}/${PORTNAME}/${PORTVERSION}/ X XMAINTAINER= corky1951@comcast.net XCOMMENT= A bin packing utility that uses a genetic algorithm X XUSE_BZIP2= yes X X.if !defined(NO_INSTALL_MANPAGES) XMAN1= ${PORTNAME}.1 X.endif X XPLIST_FILES= bin/${PORTNAME} X Xdo-install: X ${INSTALL_PROGRAM} ${WRKSRC}/src/${PORTNAME} ${PREFIX}/bin X.if !defined(NO_INSTALL_MANPAGES) X ${INSTALL_MAN} ${FILESDIR}/${PORTNAME}.1 ${MAN1PREFIX}/man/man1 X.endif X X.include <bsd.port.mk> 50e4320c645ec6fd5114d4f3ed476bc6 echo c - gaffitter/files mkdir -p gaffitter/files > /dev/null 2>&1 echo x - gaffitter/files/gaffitter.1 sed 's/^X//' >gaffitter/files/gaffitter.1 << '3d631a8c04999ac1bb2e6f18d7570e32' X.TH GAFFITTER "1" "August 2008" "gaffitter 0.6.0" "User Commands" X.SH NAME Xgaffitter \- Genetic Algorithm File Fitter X.SH SYNOPSIS X.B gaffitter X\fI-t target\fR[\fIunit\fR] [\fIoptions\fR...] \fI<files>\fR X.PP X\fIcommand\fR | \fBgaffitter\fR - \fI-t target\fR[\fIunit\fR] [\fIoptions\fR...] \fI[files]\fR X.PP Xthe unit suffixes 'k', 'm', 'g' or 't' can be used, where: X.PP Xk = KB/KiB, m = MB/MiB, g = GB/GiB and t = TB/TiB [default = bytes] X.SH DESCRIPTION XGenetic Algorithm File Fitter, GAFFitter for short, is a tool based on a genetic algorithm (GA) that tries to fit a collection of items into as few as possible volumes of a specific size. X.PP XFor example, the items might be files/directories and the volumes might be CDs or DVDs. X.PP XThe task of arranging items in such manner that the number of required bins is minimized is called Bin Packing, a NP-hard combinatorial problem for which no deterministic polynomial-time algorithm is known. Using heuristics, such as GAs, it is usually possible to approximate -- and often reach -- the best solution for the problem within a reasonable time. X.SS "General options:" X.HP X\fB\-t\fR <f>[unit], \fB\-\-target\fR <f>[unit] X.IP Xtarget size (mandatory), f>0.0 X.HP X\fB\-\-si\fR X.IP Xuse powers of 1000 (not 1024) for target, min, max and output sizes X.HP X\fB\-\-bins\fR <n>, \fB\-\-vols\fR <n> X.IP Xmaximum number of bins (volumes) [default = "unlimited"] X.HP X\fB\-v\fR, \fB\-\-verbose\fR X.IP Xverbose X.HP X\fB\-\-min\fR <f>[unit], \fB\-\-min\-size\fR <f>[unit] X.IP Xminimum file size [default = none] X.HP X\fB\-\-max\fR <f>[unit], \fB\-\-max\-size\fR <f>[unit] X.IP Xmaximum file size [default = none] X.HP X\fB\-B\fR <n>, \fB\-\-block\-size\fR <n> X.IP Xthe smallest amount of bytes a file can occupy [default = 1] X.HP X\fB\-\-ss\fR, \fB\-\-show\-size\fR X.IP Xprint the size of each file X.HP X\fB\-\-sb\fR, \fB\-\-show\-bytes\fR X.IP Xalso print the sizes in bytes X.HP X\fB\-\-hi\fR, \fB\-\-hide\-items\fR X.IP Xdon't print the selected items X.HP X\fB\-\-hs\fR, \fB\-\-hide\-summary\fR X.IP Xhide summary line containing sum, difference and number of Xselected items X.HP X\fB\-s\fR, \fB\-\-sort\-by\-size\fR X.IP Xsort the output by size, not by name X.HP X\fB\-n\fR, \fB\-\-no\-case\fR X.IP Xuse case\-insensitive sorting X.HP X\fB\-r\fR, \fB\-\-sort\-reverse\fR X.IP Xsort the output in reverse order X.HP X\fB\-z\fR, \fB\-\-null\-data\fR X.IP Xassume NULL (\e0) as the delimiter of input files via stdin (pipe) X.HP X\fB\-Z\fR, \fB\-\-null\fR X.IP Xsame as \fB\-\-dw\fR '\e0'. See also the \fB\-0\fR and \fB\-\-hs\fR options X.HP X\fB\-0\fR, \fB\-\-null\-bins\fR X.IP Xsame as \fB\-\-bs\fR '\e0'. See also the \fB\-Z\fR and \fB\-\-hs\fR options X.HP X\fB\-\-bs\fR <char>, \fB\-\-bins\-separator\fR <char> X.IP Xseparate bins (vols) with "char" [default = newline] X.HP X\fB\-\-ew\fR <char>, \fB\-\-enclose\-with\fR <char> X.IP Xenclose file names with "char" [default = none] X.HP X\fB\-\-dw\fR <char>, \fB\-\-delimit\-with\fR <char> X.IP Xdelimit file names (lines) with "char" [default = newline] X.HP X\fB\-\-version\fR X.IP Xprint GAFFitter version and exit X.HP X\fB\-h\fR, \fB\-\-help\fR X.IP Xprint this help and exit X.SS "Direct Input options:" X.HP X\fB\-\-di\fR, \fB\-\-direct\-input\fR X.IP Xswitch to direct input mode, i.e., read directly "size identifier" Xpairs instead of file names X.HP X\fB\-\-di\-b\fR, \fB\-\-di\-bytes\fR X.IP Xassume input sizes as bytes X.HP X\fB\-\-di\-k\fR, \fB\-\-di\-kb\fR X.IP Xassume input sizes as kibi bytes (KiB); KB if \fB\-\-di\-si\fR X.HP X\fB\-\-di\-m\fR, \fB\-\-di\-mb\fR X.IP Xassume input sizes as mebi bytes (MiB); MB if \fB\-\-di\-si\fR X.HP X\fB\-\-di\-g\fR, \fB\-\-di\-gb\fR X.IP Xassume input sizes as gibi bytes (GiB); GB if \fB\-\-di\-si\fR X.HP X\fB\-\-di\-t\fR, \fB\-\-di\-tb\fR X.IP Xassume input sizes as tebi bytes (TiB); TB if \fB\-\-di\-si\fR X.HP X\fB\-\-di\-si\fR X.IP Xuse powers of 1000 (not 1024) for input sizes X.SS "Genetic Algorithm options:" X.HP X\fB\-\-ga\-s\fR <n>, \fB\-\-ga\-seed\fR <n> X.IP XGA initialization seed, n>=0 [default = 1]; 0 = random X.HP X\fB\-\-ga\-rs\fR, \fB\-\-ga\-random\-seed\fR X.IP Xuse random GA seed (same as \fB\-\-ga\-seed\fR 0) X.HP X\fB\-\-ga\-ng\fR <n>, \fB\-\-ga\-num\-generations\fR <n> X.IP Xmaximum number of generations, n>0 [default = auto] X.HP X\fB\-\-ga\-ps\fR <n>, \fB\-\-ga\-pop\-size\fR <n> X.IP Xnumber of individuals, n>tournament_size [default = auto] X.HP X\fB\-\-ga\-cp\fR <f>, \fB\-\-ga\-cross\-prob\fR <f> X.IP Xcrossover probability, 0.0<=f<=1.0 [default = 0.95] X.HP X\fB\-\-ga\-mp\fR <f>, \fB\-\-ga\-mutation\-prob\fR <f> X.IP Xmutation probability, 0.0<=f<=1.0 [default = 0.10] X.HP X\fB\-\-ga\-sp\fR <n>, \fB\-\-ga\-sel\-pressure\fR <n> X.IP Xselection pressure (tournament size), 2<=n<pop_size [default = 2] X.HP X\fB\-\-ga\-theo\fR [n], \fB\-\-ga\-theoretical\fR [n] X.IP Xstop if the theoretical minimum number of bins is reached. If n is Xgiven, it is assumed to be the theoretical minimum number of bins. X.PP XOther search methods X.HP X\fB\-\-ap\fR, \fB\-\-approximate\fR X.IP Xlocal approximation using Best Fit search (non\-optimal but Xvery fast) X.HP X\fB\-\-sp\fR, \fB\-\-split\fR X.IP Xjust split the input when target size is reached (preserves Xoriginal order while splitting) X.SH LICENSE XThis is free software. You may redistribute copies of it under the terms Xof the GNU General Public License <http://www.gnu.org/licenses/gpl.html>. XThere is NO WARRANTY, to the extent permitted by law. X.SH AUTHOR XWritten by Douglas Adriano Augusto (daaugusto). 3d631a8c04999ac1bb2e6f18d7570e32 echo x - gaffitter/pkg-descr sed 's/^X//' >gaffitter/pkg-descr << 'bdb5ba88decfaec93bce0acceb30cf74' XGenetic Algorithm File Fitter, GAFFitter for short, is a tool based Xon a genetic algorithm (GA) that tries to fit a collection of items Xinto as few as possible volumes of a specific size. X XFor example, the items might be files/directories and the volumes Xmight be CDs or DVDs. X XThe task of arranging items in such manner that the number of Xrequired bins is minimized is called Bin Packing, a NP-hard Xcombinatorial problem for which no deterministic polynomial-time Xalgorithm is known. Using heuristics, such as GAs, it is usually Xpossible to approximate -- and often reach -- the best solution for Xthe problem within a reasonable time. X XWWW: http://gaffitter.sourceforge.net bdb5ba88decfaec93bce0acceb30cf74 exit --- gaffitter-0.6.0.shar ends here --- >Release-Note: >Audit-Trail: >Unformatted:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20100314025746.DAA3D106564A>